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.
