poj2406
给定一个字符串，问最多是多少个相同子串不重叠连接构成。
KMP的next数组应用。这里主要是如何判断是否有这样的子串，和子串的个数。
next数组的作用是在匹配无法进行下去时，可继续匹配的位置。这就要求next[j]必须为满足str[1..next[j]] = str[j-next[j]+1..j]的最大值。对于串的每一个前缀都取满足条件的最大值，则next[len]的值即为前一个子串的尾位置。
例如ababab，next[4]的值为2，即指向第一个b，因为str[1..2] = str[3..4]，同理next[6]的值为4，这样就使得str[1..2] = str[3..4] = str[5..6]，显然ab为满足条件的子串。
若为abababa，显然除其本身外，没有子串满足条件。而分析其next数组，next[7] = 5，next[5] = 3，next[3] = 1，即str[2..7]可由ba子串连接构成，那怎么否定这样的情况呢？很简单，若该子串满足条件，则len%sublen必为0。sunlen可由上面的分析得到为len-next[len]。
（这里可以加一个优化，长度为素数的输出为１，不过效率没见提高0 0）
因为子串是首尾相接，len/sublen即为substr的个数。
#include<cstdio> #include<cstring> char str[ 1000001] ; int next[ 1000001] ; int len ; void get_next(){ // 根据已知next推出 next[ 1] = 0 ; int j = 0 ; for( int i= 2; i<=len; i++){ while(j> 0&&str[j+ 1]!=str[i]) j = next[j] ; if(str[j+ 1]==str[i]) j ++ ; next[i] = j ; } } int main(){ while(scanf( " %s ", str+ 1)!=EOF){ if(str[ 1]== ' . ') break ; len = strlen(str+ 1) ; get_next() ; if(len%(len-next[len])== 0){ printf( " %d\n ", len/(len-next[len])) ; // for(int i=0; i<=len; i++) // printf("%d ", next[i]) ; continue ; } printf( " 1\n ") ; // for(int i=0; i<=len; i++) // printf("%d ", next[i]) ; } return 0 ;
}
poj1961
1961与 2406只是多了枚举的一步，而且要求sublen>1。
code:
#include<cstdio> char str[ 1000001] ; int next[ 1000001] ; int len ; void get_next(){ // 根据已知next推出 next[ 1] = 0 ; int j = 0 ; for( int i= 2; i<=len; i++){ while(j> 0&&str[j+ 1]!=str[i]) j = next[j] ; if(str[j+ 1]==str[i]) j ++ ; next[i] = j ; } } int main(){ int t = 0 ; while(~scanf( " %d ", &len)&&len){ scanf( " %s ", str+ 1) ; t ++ ; get_next() ; printf( " Test case #%d\n ", t) ; for( int i= 2; i<=len; i++){ if(next[i]&&i%(i-next[i])== 0) // K>1,所以加上next[i]!=0的判断 printf( " %d %d\n ", i, i/(i-next[i])) ; } printf( " \n ") ; }
}