研一离校前最后的两题了。
两题都是KMP，题意也比较相近的：给出字符串s（长度最多10^6），求模式为r^k的以s[0]开头的子串的k值。好久没写KMP了，但推了下明确思路后还是两题都1A了，对算法理解得也算还行吧……：
1961:
|
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 |
int t,sl,p[1000000],d[1000000]; char s[1000001]; int main() { int i,j,k; while(~scanf("%d%s",&sl,s)&&sl) { memset(d,0,sizeof d); p[0]=-1; d[0]=1; for(i=1,j=-1;i<sl;i++) { while(j!=-1&&s[i]!=s[j+1]) j=p[j]; if(s[i]==s[j+1]) j++; p[i]=j; if(j!=-1&&i==j+((j+1)/d[j])) d[i]=d[j]+1; else d[i]=1; } printf("Test case #%d\n",++t); for(i=0;i<sl;i++) if(d[i]>1) printf("%d %d\n",i+1,d[i]); puts(""); } return 0; } |
2406:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
int sl,p[1000000],d[1000000]; char s[1000001]; int main() { int i,j,k,l; while(~scanf("%s",s)) { sl=strlen(s); if(sl==1&&s[0]=='.') break; p[0]=-1; d[0]=1; for(i=1,j=-1;i<sl;i++) { while(j!=-1&&s[i]!=s[j+1]) j=p[j]; if(s[i]==s[j+1]) j++; if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1; else d[i]=1; } printf("%d\n",d[sl-1]); } return 0; } |
出乎意料地暑假竟然放满了。又可以制定各种不切实际的计划了吗？…