Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:怎么也想不通为什么这样是对的

Posted by angeldust at 2012-03-01 20:45:25 on Problem 1961
In Reply To:怎么也想不通为什么这样是对的 Posted by:kakassi at 2009-10-07 22:00:50
```设s1为 str[0..(next[i]-1)]    串长为next[i]

s为 str[0..(i-1)]          串长为i;

显然S1既是S2的前缀，也是S2的后缀（不是很显然？回去看下KMP吧）

因为是前缀那么s1[0]==s[0];         s1[1]==s[1]...................s1[next[i]-1]==s[next[i]-1]               ----a

因为是后缀那么s1[0]==s[i-next[i]]; s1[1]==s[i-next[i]+1].........s1[next[i]-1]==s[i-1]                     ----b

由a、b得s[0]==s[i-next[i]];       s[1]==s[i-next[i]+1]..........s2[next[i]-1]=s[i-1]                       ----c

我们设l=i-next[i];    r=next[i]%l;       k=next[i]/l;

那么c变为了 s[0]==s[l];s[1]==s[l+1]...........s[i-l-1]=s[i-1]

我们把c划分成k+1段，前k段，每段长度为l;第k+1段长度为r

那么c为

1  s[0]==s[l]...........s[l-1]==s[2*l-1];

2  s[l]==s[2*l].........s[2*l-1]==s[3*l-1];

...

...

k  s[(k-1)*l]==s[k*l]........s[k*l-1]==s[(k+1)*l-1];

k+1 s[k*l]==s[(k+1)*l].........s[i-l-1]=s[i-1];

即s[0]==s[l]==...==s[(k-1)*l]

....

....
s[l-1]==s[2*l-1]==...==s[(k+1)*l-1];

于是得出s是由长度为l的串重复(k+1)次接一个长度为r的串组成,如果r为0，则s=l^(k+1)

所以只要满足k!=0&&r为0就是一个解

即next[i]!=0&&next[i]%l==0（ps:next[i]%l==0 ==>  (next[i]+l)%l==0  ==>   i%(i-next[i])==0）```

Followed by: