KMP算法应用(一)
http://poj.org/problem?id=2406
给定一个字符串,问最多是多少个相同子串不重叠连接构成。
KMP的next数组应用。这里主要是如何判断是否有这样的子串,和子串的个数。
若为abababa,显然除其本身外,没有子串满足条件。而分析其next数组,next[7] = 5,next[5] = 3,next[3] = 1,即str[2..7]可由ba子串连接构成,那怎么否定这样的情况呢?很简单,若该子串满足条件,则len%sublen必为0。sunlen可由上面的分析得到为len-next[len]。
因为子串是首尾相接,len/sublen即为substr的个数。
若L%(L-next[L])==0,n = L/(L-next[L]),else n = 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include<iostream> #include<cstdio> using namespace std; char pattern[1000002]; int next[1000002]; /* kmp算法,需要首先求出模式串的next函数值 next[j] = k,说明 p0pk-1 == pj-kpj-1,也就是说k为其前面相等串的长度 */ void get_nextval(const char* pattern) { int i=0,j=-1; next[0]= -1; while(pattern[i] != '\0') { if(j== -1 || pattern[i]== pattern[j] ) //pattern[i]表示后缀的单个字符,pattern[j]表示前缀的单个字符 { ++i; ++j; if(pattern[i] != pattern[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; //若j值不相同,则j值回溯 } }//get_nextval int main(void) { int len; while(scanf("%s",pattern)!=EOF) { if(pattern[0]=='.') break; len=strlen(pattern); get_nextval(pattern); if(len%(len-next[len])==0) printf("%d\n",len/(len-next[len])); else printf("1\n"); } return 0; } |