POJ 2406 - Power Strings

Descryption: Check whther the string is formed by a^n, if it is, find the largest n.

Solution: If it's a^n, then n%(n-ht[rk[0]])=0, where n is the size of original string. And n/(n-ht[rk[0]]) is the answer.

Proof:
1. If answer exists, there must be a sufix whose lcp with original string is the length of that sufix, i.e., s=a^x and s'=a^(x-1).

2. The sufix is smaller than original string in sufix array.

3. Assume the answer sufix is not the sa[rk[0]-1], but sa[rk[0]-y] (y>1).

We let s1=sufix(sa[rk[0]-y]), s2=sufix(sa[rk[0]-y+1]), s=original string.

We let |s1|=lcp(s, s1). Then lcp(s, s2)>=cur...(1) and lcp(s1, s2)>=cur...(2).

Since (2),  sa[rk[0]-y+1] has the smaller index than sa[rk[0]-y].

Let's denote Y=sa[rk[0]-y], Z=sa[rk[0]-y+1], b1=s[0..Z-1], b2=s[Z..Y-1], b=s[0..Y-1]. Thus b=b1|b2 and b^x'=s.

From the definition ,we get s1=b^(x'-1), s2=b2|b^(x'-1). From (2), we get b^(x'-1) = b2|b^(x'-2)|b1 ----> (b1|b2)^(x'-1) = (b2|b1)^(x'-1) ----> b1|b2 = b2|b1 = b...(3)

From (3), we get lcp(b, b2)=|b2|...(4)

From (3), (4), we get lcp(s=b^x'=b^(x'-1)|b, s2=b^(x'-1)|b2) = |s2|...(5)

From (5), we can infer that for all 0<=i<=y, lcp(s, sufix(sa[rk[0]-i])) = |sufix(sa[rk[0]-i])|. i.e., if I is the factor of n, it has longer repeatetion than Y.

That is, if the answer is Y, |b1| is not the factor of n. Since |b| is the factor of n, thus |b1|, |b2| is not the factor of |b|.

Denote p=|b|/|b1|, q=|b|%|b1|<>0, r=b[|b|-q...|b|-1].

Since b1|b2=b2|b1=b. lcp(b=b1|b2, b2)=|b2|. Thus b[x]=b2[x]=b[x+|b1|](x+|b1|<|b|) ----> b=b1^p|r.

Since b1|b2=b2|b1=b. lcs(b=b2|b1, b2)=|b2|. Thus b[x]=b2[x]=b[x-|b1|](x-|b1|>=0)  ----> b=r|b1^p.

Let's denote c1=r, c2=b1^p. We get b=c1|c2=c2|c1.

Repeat the above operation, and finally we get b=*1|*2=*2|*1 where |*1| is the factor of |b|. s*=*2|b^(x'-1) must be the sufix between s2 and s (since lcp(s, s*)=|s*| and the start index is smaller than s2). In addition, |*1| is the factor of |b|, thus it's the factor of n, and s=*1^x" (x">x').

Finally, it contradict with the assumption that the answer is sufix(sa[rk[0]-y]) where y>1.

Status: TLE - since the O(nlogn) sufix array is too costy. However, the proof above can also use in the KMP and LSA to get the answer.