-47. Play with Words, Too

Task Description

Write a program (again) to play with words. Your program should support the following commands.

• insert left x n
  Insert $n$ characters of $x$ at the beginning of a word.
• insert right x n
  Insert $n$ characters of $x$ at the end of a word.
• insert k x n
  Insert $n$ characters of $x$ so that the first of them will become the $k$-th character of this word.
• print
  Print the current content of the word in the following format: if the word is gooooooooooooooooooooooooooogle, you should print g 1 o 27 g 1 l 1 e 1 $\lt /code>. In other words, you should encode all consecutive sequences with the same character into character-length pairs, then print a dollar sign to indicate the end of the word.\lt /li> \lt /ul> \lt p class="has-jax has-jax has-jax">Where \lt span class="MathJax_Preview" style="color: inherit;">\lt /span>\lt span class="MathJax" data-mathml='<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>' id="MathJax-Element-8-Frame" role="presentation" style="position: relative;" tabindex="0">\lt nobr aria-hidden="true">\lt span class="math" id="MathJax-Span-22" role="math" style="width: 0.609em; display: inline-block;">\lt span style="display: inline-block; position: relative; width: 0.562em; height: 0px; font-size: 103%;">\lt span style="position: absolute; clip: rect(1.589em, 1000.52em, 2.289em, -999.998em); top: -2.145em; left: 0.002em;">\lt span class="mrow" id="MathJax-Span-23">\lt span class="mi" id="MathJax-Span-24" style="font-family: MathJax_Math-italic;">x\lt /span>\lt /span>\lt span style="display: inline-block; width: 0px; height: 2.149em;">\lt /span>\lt /span>\lt /span>\lt span style="display: inline-block; overflow: hidden; vertical-align: -0.046em; border-left: 0px solid; width: 0px; height: 0.579em;">\lt /span>\lt /span>\lt /nobr>\lt /span>\lt script id="MathJax-Element-8" type="math/tex">x\lt /script> is a alphanumeric character and both \lt span class="MathJax_Preview" style="color: inherit;">\lt /span>\lt span class="MathJax" data-mathml='<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>' id="MathJax-Element-9-Frame" role="presentation" style="position: relative;" tabindex="0">\lt nobr aria-hidden="true">\lt span class="math" id="MathJax-Span-25" role="math" style="width: 0.656em; display: inline-block;">\lt span style="display: inline-block; position: relative; width: 0.609em; height: 0px; font-size: 103%;">\lt span style="position: absolute; clip: rect(1.589em, 1000.61em, 2.289em, -999.998em); top: -2.145em; left: 0.002em;">\lt span class="mrow" id="MathJax-Span-26">\lt span class="mi" id="MathJax-Span-27" style="font-family: MathJax_Math-italic;">n\lt /span>\lt /span>\lt span style="display: inline-block; width: 0px; height: 2.149em;">\lt /span>\lt /span>\lt /span>\lt span style="display: inline-block; overflow: hidden; vertical-align: -0.046em; border-left: 0px solid; width: 0px; height: 0.579em;">\lt /span>\lt /span>\lt /nobr>\lt /span>\lt script id="MathJax-Element-9" type="math/tex">n\lt /script> and \lt span class="MathJax_Preview" style="color: inherit;">\lt /span>\lt span class="MathJax" data-mathml='<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>' id="MathJax-Element-10-Frame" role="presentation" style="position: relative;" tabindex="0">\lt nobr aria-hidden="true">\lt span class="math" id="MathJax-Span-28" role="math" style="width: 0.562em; display: inline-block;">\lt span style="display: inline-block; position: relative; width: 0.516em; height: 0px; font-size: 103%;">\lt span style="position: absolute; clip: rect(1.309em, 1000.52em, 2.289em, -999.998em); top: -2.145em; left: 0.002em;">\lt span class="mrow" id="MathJax-Span-29">\lt span class="mi" id="MathJax-Span-30" style="font-family: MathJax_Math-italic;">k\lt /span>\lt /span>\lt span style="display: inline-block; width: 0px; height: 2.149em;">\lt /span>\lt /span>\lt /span>\lt span style="display: inline-block; overflow: hidden; vertical-align: -0.046em; border-left: 0px solid; width: 0px; height: 0.82em;">\lt /span>\lt /span>\lt /nobr>\lt /span>\lt script id="MathJax-Element-10" type="math/tex">k\lt /script> are positive integers.\lt /p> \lt p>Note that you need to implement this word as a binary tree, otherwise it it very likely that you will run out of time because you need to run through the data structure in order to find the correct location for insertion. You may want to store the number of characters in a node, as well as the number of characters in the sub-tree to speed thing up.\lt /p> \lt h2 class="content-subhead">Input\lt /h2>\lt p class="has-jax has-jax">The input data contains a sequence of commands described above. You may assume that all commands are valid. That is, \lt span class="MathJax_Preview" style="color: inherit;">\lt /span>\lt span class="MathJax" data-mathml='<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>' id="MathJax-Element-11-Frame" role="presentation" style="position: relative;" tabindex="0">\lt nobr aria-hidden="true">\lt span class="math" id="MathJax-Span-31" role="math" style="width: 0.562em; display: inline-block;">\lt span style="display: inline-block; position: relative; width: 0.516em; height: 0px; font-size: 103%;">\lt span style="position: absolute; clip: rect(1.309em, 1000.52em, 2.289em, -999.998em); top: -2.145em; left: 0.002em;">\lt span class="mrow" id="MathJax-Span-32">\lt span class="mi" id="MathJax-Span-33" style="font-family: MathJax_Math-italic;">k\lt /span>\lt /span>\lt span style="display: inline-block; width: 0px; height: 2.149em;">\lt /span>\lt /span>\lt /span>\lt span style="display: inline-block; overflow: hidden; vertical-align: -0.046em; border-left: 0px solid; width: 0px; height: 0.82em;">\lt /span>\lt /span>\lt /nobr>\lt /span>\lt script id="MathJax-Element-11" type="math/tex">k\lt /script> would not exceed the current length of the word plus 1. The total length of the word would less then \lt span class="MathJax_Preview" style="color: inherit;">\lt /span>\lt span class="MathJax" data-mathml='<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>2147483647</mn></math>' id="MathJax-Element-12-Frame" role="presentation" style="position: relative;" tabindex="0">\lt nobr aria-hidden="true">\lt span class="math" id="MathJax-Span-34" role="math" style="width: 5.137em; display: inline-block;">\lt span style="display: inline-block; position: relative; width: 4.997em; height: 0px; font-size: 103%;">\lt span style="position: absolute; clip: rect(1.309em, 1005em, 2.289em, -999.998em); top: -2.145em; left: 0.002em;">\lt span class="mrow" id="MathJax-Span-35">\lt span class="mn" id="MathJax-Span-36" style="font-family: MathJax_Main;">2147483647\lt /span>\lt /span>\lt span style="display: inline-block; width: 0px; height: 2.149em;">\lt /span>\lt /span>\lt /span>\lt span style="display: inline-block; overflow: hidden; vertical-align: -0.046em; border-left: 0px solid; width: 0px; height: 0.82em;">\lt /span>\lt /span>\lt /nobr>\lt /span>\lt script id="MathJax-Element-12" type="math/tex">2147483647\lt /script>.\lt /p> \lt h2 class="content-subhead">Output\lt /h2>\lt p>You should output the content of the word in the compressed format described above whenever you read the \lt code>print\lt /code> command.\lt /p> \lt h2 class="content-subhead">Sample input\lt /h2>\lt pre>\lt code>\lt span class="fw-code-copy-button pure-button">\lt i class="fa fa-clipboard">\lt /i>\lt /span>\lt div class="syntaxhighlighter nogutter" id="highlighter_520795">\lt table border="0" cellpadding="0" cellspacing="0">\lt tbody>\lt tr>\lt td class="code">\lt div class="container">\lt div class="line number1 index0 alt2">\lt code class="plain">print\lt /code>\lt /div>\lt div class="line number2 index1 alt1">\lt code class="plain">insert left g 2\lt /code>\lt /div>\lt div class="line number3 index2 alt2">\lt code class="plain">insert right e 1\lt /code>\lt /div>\lt div class="line number4 index3 alt1">\lt code class="plain">insert 3 l 1\lt /code>\lt /div>\lt div class="line number5 index4 alt2">\lt code class="plain">insert 2 o 2\lt /code>\lt /div>\lt div class="line number6 index5 alt1">\lt code class="plain">print\lt /code>\lt /div>\lt div class="line number7 index6 alt2">\lt code class="plain">insert 4 o 25\lt /code>\lt /div>\lt div class="line number8 index7 alt1">\lt code class="plain">print\lt /code>\lt /div>\lt /div>\lt /td>\lt /tr>\lt /tbody>\lt /table>\lt /div> \lt /code>\lt /pre>\lt h2 class="content-subhead">Sample output\lt /h2>\lt pre>\lt code>\lt span class="fw-code-copy-button pure-button">\lt i class="fa fa-clipboard">\lt /i>\lt /span>\lt div class="syntaxhighlighter nogutter" id="highlighter_121956">\lt table border="0" cellpadding="0" cellspacing="0">\lt tbody>\lt tr>\lt td class="code">\lt div class="container">\lt div class="line number1 index0 alt2">\lt code class="plain">$