# Stuttering Subsequence Problem - Explain the example

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:

x=0120002112022220110001

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.

• 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.
– WimC
Mar 1, 2015 at 20:35
• You mean treat for example $0000$ as one $0$? Mar 1, 2015 at 20:37
• 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 Mar 1, 2015 at 20:39
• No. Strike through every second $0$: $0 \not 0\, 0 \not 0$.
– WimC
Mar 1, 2015 at 20:39
• Thank you! I understand now. feel free to write an answer. I will accept it. thank you very much. Mar 1, 2015 at 20:41

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.