学步园

与next[],相关的常用用法.1:求字符串的重复数.当while(i%i-next[i]==0),重复数为(i/i-next[len];) 练习题(poj 2406 1961)

2:len-next[len]为一个重复子串的基串个数,比如a表示基串,a^k,第一个用法求的是k,而第二个求的是a的个数.

值得注意的是ababa的基串也为2,为什么?自己想想哈.

3.深刻理解next的含义.练习题(poj 2752)

思路：KMP很好的一道题。首先易证：最小覆盖子矩阵一定靠左上角。那么，我们考虑求出每一行的最小重复串长度，所有行的最小重复串的长度的lcm就是最小重复子矩阵的宽。然后我们对列也做相同的操作。于是我们就可以求得最小重复子矩阵的大小了。（这里要注意一点：当所得的宽大于原来的宽时，就让等于原来的宽，长也如此）。算法实现：算法的核心在于高效的求出每一行和每一列的最小重复串，这个可以最原串做一次KMP中的get_next()。（注：以上部分为转载）

这道题对我这个字符串菜鸟来说实在是有些难；一来是就想来个暴力，但想了想，

可定超时，于是看了discuss，用KMP来优化，求每一行每一列的求最小覆盖；

但是我完全没有思路，看了一下解题报告，原来才知道用的是第二类KMP求next

数组，算法是理解了，

但是对于为什么最小覆盖就等于i-next[i]还不懂？？？

#include<iostream><br /> #include<stdio.h><br /> using namespace std;<br /> char s[10005][80];<br /> int subrow[10005];<br /> int subcol[80];<br /> int next[10005];<br /> int row,col;<br /> int nextrow(int r)<br /> {<br /> int i=0,j=-1;<br /> next[0]=-1;<br /> while(i<col)<br /> {<br /> if(j==-1||s[r][i]==s[r][j])<br /> {<br /> i++;j++;<br /> next[i]=j;<br /> }<br /> else<br /> j=next[j];<br /> }<br /> return i-next[i];//这里我还是没弄懂会有最小覆盖于最大重复字串的和为i；<br /> }<br /> int nextcol(int c)<br /> {<br /> int i=0,j=-1;<br /> next[0]=-1;<br /> while(i<row)<br /> {<br /> if(j==-1||s[i][c]==s[j][c])<br /> {<br /> i++;j++;<br /> next[i]=j;<br /> }<br /> else<br /> j=next[j];<br /> }<br /> return i-next[i];<br /> }</p> <p>int LCM(int a,int b)<br /> {<br /> int x=a,y=b;<br /> int r=x%y;<br /> while(r>0)<br /> {<br /> x=y;<br /> y=r;<br /> r=x%y;<br /> }<br /> return a*b/y;<br /> }<br /> int main()<br /> {<br /> while(scanf("%d%d",&row,&col)==2)<br /> {<br /> for(int i=0;i<row;i++)<br /> scanf("%s",s[i]);<br /> for(int i=0;i<row;i++)<br /> subrow[i]=nextrow(i);<br /> for(int i=0;i<col;i++)<br /> subcol[i]=nextcol(i);<br /> int x=1;<br /> for(int i=0;i<row;i++)<br /> x=LCM(x,subrow[i]);<br /> if(x>col)<br /> x=col;<br /> int y=1;<br /> for(int i=0;i<col;i++)<br /> y=LCM(y,subcol[i]);<br /> if(y>row)<br /> y=row;<br /> printf("%d/n",x*y);<br /> }<br /> return 0;<br /> }<br />