How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation and stripping first and last character? E.g s = xyzxyz, subsequence is xyz and it occurs 2 times. The solution is to concatenate the same string e.g. xyzxyzxyzxyz and then strip the first and last character to get yzxyzxyzxy, then you find s (xyzxyz) inside that.

Other examples:

  1. The word Table does not have a subsequence so the above method will give: Table||Table -> TableTable -> ableTabl -> which does not contain Table so Table does not contain a subsequence
  2. The word mmebmmebmmeb -> has to return true with the above method because it contains mmeb repeated 3 times. So, mmebmmebmmeb || mmebmmebmmeb -> mmebmmebmmebmmebmmebmmeb -> (strip first and last) mebmmebmmebmmebmmebmme which contains mmebmmebmmeb (meb**mmebmmebmmeb**mmebmme)

My thought was to assume that there is at least one character in s that will invalidate the occurrence of a subsequence. E.g. instead of xyzxyzxyz (xyz occurring three times) we have xyzxyzxya where a is the wrong char. Now we assume that in yzxyzxyaxyzxyzxy (after concatenation and stripping first and last) that the string s does exist which should be a contradiction - but I am stuck.

Could someone give me a formal mathematical proof?

Looked at this for ideas: How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

  • $\begingroup$ I don't understand your question. If we're allowed $n=1$, it's trivial: the string MattIsGreat is one copy of xMattIsGreatx with the first and last character removed. If we're not allowed $n=1$, then the thing you're trying to prove is false, since MattIsGreat can't be written as two or more copies of anything. $\endgroup$ – David Richerby Aug 18 '18 at 8:55
  • $\begingroup$ Yes, I changed to n > 1. You are right MattIsGreat does not have a subsequence that's why the method above returns false. If we have MattMatt then the above method returns true MattMattMattMatt => attMattMattMat and MattMatt is present $\endgroup$ – Matt Aug 18 '18 at 9:24
  • $\begingroup$ OK (and I see that, actually, you had that case covered in your examples). But I'm still not sure what you're trying to prove. Your first sentence is, basically, "How can I prove this thing that isn't true for all strings?", to which the answer is "You can't, unless you restrict the choice of strings, because it's not true for a general string $s$." So what is it that you want a proof of? $\endgroup$ – David Richerby Aug 18 '18 at 9:31
  • $\begingroup$ If there exists a string, s which can be formed using repeated subsequences what is the mathematical proof showing that concatenation and stripping first and last characters returns true if the string was made up of the subsequence, otherwise false $\endgroup$ – Matt Aug 18 '18 at 10:08
  • $\begingroup$ OK, I see where you're going. You've described an algorithm to solve the problem "Does this string have property X?" and you're trying to prove that the algorithm is correct. I was trying to edit to hopefully clarify that, but then I realised that your solution to the first example, $xyzxyz$, makes the problem trivial again. Every nonempty string $s$ is a substring of $sss$ with the first and last characters removed. For example, MattIsGreat is a substring of attIsGreatMattIsGreatMattIsGrea. I thought you wanted $s$ to be $t^n$ minus the first and last chars, not just a substring of it. $\endgroup$ – David Richerby Aug 18 '18 at 10:16

Let us first state the theorem that we are trying to prove.

Theorem. Let $w \neq \epsilon$ be a word. Then $w^2 = xwy$ for $x,y \neq \epsilon$ if and only if $w = z^p$ for some $p > 1$.

Proof. Let us first suppose that $w = z^p$ for some $p > 1$. Then $w^2 = z^{2p} = zwz^{p-1}$, where $z,z^{p-1} \neq \epsilon$.

In the other direction, write $w = w_1w_2$, where $|xw_1| = |w_2y| = |w|$. Since $x,y \neq \epsilon$, we see that $|w_1|,|w_2| < |w|$. We have $ww = xw_1w_2y$ implies that $w = xw_1 = w_2y$, and so $x = w_2$ (since $|x| = |w|-|w_1| = |w_2|$). In other words, $w = w_2w_1$.

Now let $w = \sigma_0 \ldots \sigma_{n-1}$, and let $|w_2| = m$. Note that since $|w_1|,|w_2| < n$, we have $0 < m < n$. The equality $w = w_2w_1$ implies (check!) that $\sigma_i = \sigma_{i+m \bmod{n}}$. Let $g$ be the GCD of $m$ and $n$; note that $g < n$. It is known that $g = am + bn$ for some integers $a,b$, and so $\sigma_i = \sigma_{i+bm \bmod{n}} = \sigma_{i+g \bmod{n}}$. Since $g \mid n$, this implies that $w = (\sigma_1 \ldots \sigma_g)^{n/g}$, where $n/g > 1$.


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.