标签为 [KMP] 的文章

HDU 3746 Cyclic Nacklace

我能表示自己不会做吗。 好吧。 其实这道题就是个裸的KMP 但我一开始竟然没有看出来 显而易见的是,如果要添加几个字符的话,肯定是字符串的循环节缺了一部分 所以答案是 (n-fail[n])-n%(n-fail[n]) Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char st[210000]; int n; int s[210000]; int main() { int T; scanf("%d",&T); while (T--) { scanf("%s",st+1); n=st ......

HDU 2594 Simpsons’ Hidden Talents

这道就是纯KMP,QAQ。 你只要把这两个字符串合在一起求一遍KMP就可以了 注意最后输出的总长度必须小于等于min(len1,len2). Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char st[110000],st1[110000],st2[110000]; int s[110000]; int n,cnt,n1,n2; int main() { while (scanf("%s%s",st1+1,st2+1)!=EOF) { n1=strlen(st1+1); n2=strlen(st2+1); for (int i=2;i<=n1;i++) { int t=s[i-1]; while (t ......

HDU 2434 Period

继续切水题的我。 这道题算法KMP 然后你只需要在做KMP的时候看一下i%(i-next[i])是否等于0且next[i]不为0 如果是0说明这里有循环节(不信你可以自己模拟一下QAQ) Code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; using namespace std; char st[1100000]; int s[1100000]; int n,cnt; int main() { scanf("%d",&amp;n); while (n) { cnt++; printf("Test case #%d\n",cnt); scanf("%s",st+1); for (int i=2;i&lt;=n ......

BZOJ 1009 GT考试

这道可以用KMP 很显然又是一个模板题 只不过因为n太大了,于是用了矩阵乘法 你只要先预处理出fail数组, 然后转移矩阵也就可以求出来了, 你只需要枚举每个前缀的转移,假设枚举前缀i,有一个转移是j,你就在g[i][j]上+1 不过注意如果转移为m的话就continue 代码还是很短。 Code: #include<cstdio> #include<algorithm> using namespace std; int n,m,MOD; char st[22]; int s[22]; long long f[22][22],df[22][22],dg[22][22],dgg[22][22],g[22][22]; int main() { scan ......