题解 UVA10298 【Power Strings】

这里是对目前最高赞题解结论的证明。 结论：设字符串长度为$n$，最长相同前后缀的长度为$next[i]$， 如$n$%$(n-next[n])=0$，则答案为$n/(n-next[n])$，否则为$1$。 证明： 我们求$next$数组的时候，相当于每次把当前串这样对齐了一下↓  而$next$求到$n$时，上面串的$n$对应的就是下面串的$next[n]$。  这时候的$n-nxt[n]$就是箭头指向的绿色部分。  而上下两串其实是一样的，所以下面串的前$n-nxt[n]$格和上面串的前$n-nxt[n]$相同。 又因为两串由蓝色框住的部分匹配，所以下面的绿框对应的部分和绿框相同。  依此递推，可以得到，**如果循环节多于一个**，以前$n-nxt[n]$个为循环节，是可以铺满整串的。而且因为$nxt[n]$是尽量大的，所以这样得到的循环节长度为所有可能情况中最小的，也就是我们所求的。 而如果$n$%$(n-next[n])≠0$，可以认为之前的循环节匹配仍然可以进行，但是最后一个循环节被强行割掉了一些。  显然这样就怎么都安排不上了。 所以如$n$%$(n-next[n])=0$，就能排上，答案为$n/(n-next[n])$，否则只能以自己为循环节，答案为$1$。 代码实现的时候注意一下自己代码中$n$的定义和$nxt$数组的定义什么的。 还是放一下我的代码叭qwq ``` /* qwerta UVA10298 Power Strings Accepted 代码 C++，0.65KB 提交时间 2018-10-12 17:59:53 耗时/内存 100ms, 0KB */ #include<iostream> #include<cstdio> using namespace std; int nxt[1000003]; int main() { //freopen("a.in","r",stdin); while(1) { string s; getline(cin,s);//读入一整行，放进s if(s.length()==1&&s[0]=='.')break; int lens=s.length(); //kmp求next int k=-1; nxt[0]=-1; for(register int i=1;i<lens;++i) { while(k!=-1&&s[i]!=s[k+1])k=nxt[k]; if(s[i]==s[k+1])k++; nxt[i]=k; } int n=lens-1; if((n+1)%(n-nxt[n])==0)//如果能恰好排满循环节 printf("%d\n",((n+1)/(n-nxt[n])));//输出总长除以循环节长度 else printf("1\n");//否则输出1 } return 0; } ``` ------------ 以上18.10.17 20.12.7更新： 关于讨论中提到的“可能有比(n-nxt[n])更长的目标子串”，可证该情况不存在，证明如下： 反证：如果存在，则有如图情况： [](https://imgchr.com/i/DxrvPU) 即左上方绿色段+橙色段=右下方黄色段+绿色段。 则推出左上方绿色段由黄色段开头，且两个绿色段相同。 推出右下方绿色段由黄色段开头...（这个递推和前文的递推类似 最后得出该目标子串由黄色小段重复而成，和题目要求的“最短字串”不符。 所以不存在比(n-nxt[n])更长的目标子串，原结论正确。 //~~没想到都大学了我还能看懂当年的题解，泪目~~