首先看我对kmp解决周期、前缀与后缀间关系的解释

http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

hdu 3336  count the string

题意：求给定字符串含前缀的数量

abab

前缀为

a

ab

aba

abab

abab中共有六个子串是前缀a a ab ab aba abab

所以答案为6

利用kmp中的匹配原理可以完美的解决此题

 a---------d-----

   -----a---------d

               i         j

如上所示，假设两串字符完全相等，next[j]=i,代表s[1...i]==sum[j-i+1....j]，这一段其实就是前缀

i~j之间已经不可能有以j结尾的子串是前缀了，不然next【j】就不是 i 了

设dp【i】:以string[i]结尾的子串总共含前缀的数量

所以dp[j]=dp[i]+1，即以i结尾的子串中含前缀的数量加上前j个字符这一前缀

View
Code

hdu  3746  Cyclic
Nacklace 

求最少需要在结尾后面补几个字符才能凑成两个循环

kmp最小循环节的应用http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

hdu  1358 period 

求某个前缀含几个循环

典型的利用next【】求周期的题目

hdu 2087

这里要注意匹配的时候如果成功了，直接把j指针赋值为0

因为

aaa   aa

只匹配一次

hdu 2594

错了6次，7A的题目。。。不够细心啊

题目要求最长的a的前缀同时满足是b的后缀

先把后面的那串字符串接到前面的字符串的后面

利用next的特性，如果next【len（a+b）】> len(a)  ,继续利用next【next【len(a+b)】】来比较

如果next【len（a+b）】> len(b)  ,继续利用next【next【len(a+b)】】来比较

两组数据很好的解释了这个操作

abcabcabcabc

abcabcabcabcabc

12

abcabc

abc

3