I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$.

The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf

Some background on the problem for those who do not know it: Suppose $A$ is a string of $n$ letters, and $B$ is a string of $m$ letters.

$B$ is said to be a subsequence of $A$ if $A$ has all the letters of $B$, in the same order as $B$, but not necessarily one after the other.

Example: $A=1,1,2,2,0,2$ and $B=1,0$ then $B$ is a subsequence of $A$, because $A$ has $1$ and then $0$ some spots after it. if $B=0,1$ then it would not have been a subsequence because there is no $1$ after the $0$ in $A$.

We define $B^{i}$ as a string with the same letters as $B$, only now each letter appears $i$ times. Example: if $B=0,1,1,2$ then $B^{2}=0,0,1,1,1,1,2,2$

Our goal is to find the maximum $i$ for which $B^{i}$ is a subsequence of $A$. The writers of the article I'm reading managed to do it in linear time, but I can't understand the example they gave.

In page 3 they define a function called half(x) [where x is a string] that returns a string that is a subsequence of x and roughly half the size of x defined as such:

consider a letter $\sigma$, let the positions of x at which $\sigma$ appears be $j_1,j_2,j_3,...$

drop the positions $j_k$ where $k$ is even and only consider $j_1,j_3,...$. the sequence half(x) is obtained by the above routine on all the letters of x.

And here is the example they gave which I don't understand:


then half(x)=012012022100

if you read just that page in the article it will be much clearer. it's page 3 on the right side. relatively short.

I don't understand at all why that's the case. I followed their method for half(x) and what i get is half(x)=02021022100.

  • $\begingroup$ Example: consider all $0$'s in that sequence. Now strike through every second occurence, not every $0$ at an even index. Do the same for all other symbols. $\endgroup$
    – WimC
    Mar 1, 2015 at 20:35
  • $\begingroup$ You mean treat for example $0000$ as one $0$? $\endgroup$ Mar 1, 2015 at 20:37
  • $\begingroup$ that doesn't seem to work either, because x=012000211... if i were to strike through the second occurence of $0$ then half(x)=012211... and it isn't in the example they gave $\endgroup$ Mar 1, 2015 at 20:39
  • $\begingroup$ No. Strike through every second $0$: $0 \not 0\, 0 \not 0$. $\endgroup$
    – WimC
    Mar 1, 2015 at 20:39
  • $\begingroup$ Thank you! I understand now. feel free to write an answer. I will accept it. thank you very much. $\endgroup$ Mar 1, 2015 at 20:41

1 Answer 1


Example: consider all $0$'s in that sequence. Now strike through every second occurence of $0$ regardless of the parity of its index. Do the same for all other symbols.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.