转载：http://blog.csdn.net/shahdza/article/details/6303578
Count the string
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1147 Accepted Submission(s): 494
s: "abab"
The prefixes are: "a", "ab", "aba", "abab"
For each prefix, we can count the times it matches in s. So we can see that prefix "a" matches twice, "ab" matches twice too, "aba" matches once, and "abab" matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For "abab",
it is 2 + 2 + 1 + 1 = 6.
The answer may be very large, so output the answer mod 10007.
For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.
1 4 abab
6
#include<stdio.h>
const int mod=10007;
char s[222222];
int next[222222];
void getnext(int x) {
int i=0,j=-1;
next[0]=-1;
while(i<x) {
if(j==-1||s[i]==s[j]) {
i++;j++;
next[i]=j;
}
else j=next[j];
}
}
int main()
{
int t,i,x;
scanf("%d",&t);
while(t--) {
scanf("%d%s",&x,s);
getnext(x);
int ans=x;
for(i=0;i<=x;i++)
//关键在这里，next的值就是和前缀匹配的个数，
if(next[i]+1!=next[i+1])
ans=(ans+next[i])%mod;
printf("%d/n",ans);
}
}
转载：http://blog.csdn.net/niushuai666/article/details/6965517
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3746
题目大意：
给你一个字符串，要求将字符串的全部字符最少循环2次需要添加的字符数。
例子：
abcabc 已经循环2次，添加数为0
abcac 没有循环2次，添加字符abcac。数目为5.
abcabcab 已经循环过2次，但第三次不完整，需要添加数为1
解题思路：
next[]数组的运用。
这里需要深刻理解next数组的含义，所以需要花费一定的功夫去弄懂这些。。
对于next数组，经过3天的学习，有了一定的认识。自己总结一下吧。
首先，求next数组有两种方法。第一种是严蔚敏教授那本数据结构上的求法。代码如下：
void getnext(const char *s)
{
int i = 0, j = -1;
nextval[0] = -1;
while(i != len)
{
if(j == -1 || s[i] == s[j])
nextval[++i] = ++j;
else
j = nextval[j];
}
}
这种求法的含义是：
next[i]代表了前缀和后缀的最大匹配的值（需要彻底明白这点，相当重要）
另外一种是对这种算法的改进版本，代码如下：
void getnext(const char *p) //前缀函数(滑步函数)
{
int i = 0, j = -1;
nextval[0] = -1;
while(i != len)
{
if(j == -1 || p[i] == p[j]) //(全部不相等从新匹配 || 相等继续下次匹配)
{
++i, ++j;
if(p[i] != p[j]) //abcdabce
nextval[i] = j;
else //abcabca
nextval[i] = nextval[j];
}
else
j = nextval[j]; //子串移动到第nextval[j]个字符和主串相应字符比较
}
}
改进的地方在于-1的运用，关于怎么优化我已经写过了。自己看下就行了。。。但是一定要明白。
不同之处：
没有优化的getnext函数，next数组存的是前缀和后缀的最大匹配值，而优化后的getnext函数存的是在这个基础，进行更高效的改进。
比如abcabca
改进前最后一个字符next[7]=4,表示的是前缀和后缀最大匹配是4，即abca和abca。
改进后的next[7]=-1。这点也需要彻底搞懂，才能灵活的运用next函数。
总结一下：
在求前缀和后缀的最大匹配值时，要使用第一种，也就是未优化的算法。在运用KMP时，使用第二种算法，因为避免了多余的判断，更加高效。
YY：
其实我们可以发现KMP算法的精华部分是一个DP。每次右滑时，都是根据前面状态得到的有用信息进行的。相当于记忆化更新。这样算法才具有了很高的效率。
当然，理解这个算法确实需要仔细反复的研究，反正我是看了3天，才把这点基础东西搞的差不多，算是理解了80%吧。剩下的在以后做题的过程中慢慢发现吧。。。。
这道题的代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100010
char s[N];
int nextval[N];
int len;
void getnext(const char *s)
{
int i = 0, j = -1;
nextval[0] = -1;
while(i != len)
{
if(j == -1 || s[i] == s[j])
nextval[++i] = ++j;
else
j = nextval[j];
}
}
int main()
{
int ncase;
int length, add;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%s", s);
len = strlen(s);
getnext(s);
/*for(int i = 0; i <= len; ++i) //查看next数组的内容
cout<<nextval[i]<<" ";
cout<<endl;*/
length = len - nextval[len]; //循环节的长度
if(len != length && len % length == 0) //循环多次
printf("0\n");
else
{
add = length - nextval[len] % length; //取余的作用：abcab，去掉abc
printf("%d\n",add);
}
}
return 0;
}
http://blog.csdn.net/pzler/article/details/20312163
循环字符串的最小表示法的问题可以这样描述：
对于一个字符串S，求S的循环的同构字符串S’中字典序最小的一个。
由于语言能力有限，还是用实际例子来解释比较容易：
设S=bcad，且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。
对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。
一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。
令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k，分别从i和j位置向下比较，直到S[i] != S[j]
如果S[i+k] > S[j+k] i=j,j=i+1
否则j++
返回i
起初，我想在j指针后移的过程中加入一个优化。就是j每次不是加1，而是移动到l位置。其中，l>j且S[l]<=S[j]。但是，即使加入这一优化，在遇到bbb…bbbbbba这样的字符串时复杂度将退化到O(n^2)。
注意到，朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。
令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k，分别从i和j位置向下比较，直到S[i] != S[j]
如果S[i+k] > S[j+k] i=i+k
否则j++
返回i和j的小者
注意到上面两个算法唯一的区别是粗体的一行。这一行就把复杂度降到O(n)了。
值得一提的是，与KMP类似，最小表示法处理的是一个字符串S的性质，而不是看论文时给人感觉的处理两个字符串。
应用最小表示法判断两个字符串同构，只要将两个串的最小表示求出来，然后从最小表示开始比较。剩下的工作就不用多说了。
int MinimumRepresentation(char *s, int l)
{
int i = 0, j = 1, k = 0, t;
while(i < l && j < l && k < l) {
t = s[(i + k) >= l ? i + k - l : i + k] - s[(j + k) >= l ? j + k - l : j + k];
if(!t) k++;
else{
if(t > 0) i = i + k + 1;
else j = j + k + 1;
if(i == j) ++ j;
k = 0;
}
}
return (i < j ? i : j);
}
【KMP】poj 1961 Period(KMP, 最短循环节)
http://blog.csdn.net/shuangde800/article/details/8114700
题目链接：
POJ ： http://poj.org/problem?id=1961
HDU ： http://acm.hdu.edu.cn/showproblem.php?pid=1358
ZOJ ： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2177
题目大意：
给定一个长度为n的字符串s，求它的每个前缀的最短循环节。换句话说，对于每个i（2<=i<=n）,求一个最大的整数K>1（如果K存在），使得S的前i个字符组成的前缀是某个字符串重复K次得到的。输出所有存在K的i和对应的K。
比如对于字符串aabaabaabaab, 只有当i=2,6,9,12时K存在，且分别为2,2,3,4
分析与总结：
很经典的一道题目， 各大OJ都有收录。
开始做这题的时候，刚刚看懂KMP，没看最短循环节的相关资料，自己乱搞，花了两节离散数学课想，结果终于AC了 = =， 但不幸的是，结果发现只是再HDU和ZOJ过了，而poj的还是WA 。。。
然后学习《算法入门经典-训练指南》上面的方法，在poj上才成功AC。
虽然没能在poj上成功AC，但是经过这题的思考，对KMP的失配函数获取next的过程和原理有了更深的理解和体会。
代码：
从刘汝佳的大白书（算法入门经典-训练指南）学来的方法。
#include<cstdio>
#include<cstring>
const int MAXN = 1000005;
char T[MAXN];
int f[MAXN];
int n;
void getFail(char *P, int *f){
f[0]=f[1]=0;
int start=1;
int n=strlen(P);
for(int i=1; i<n; ++i){
int j=f[i];
while(j && P[i]!=P[j]) j=f[j];
f[i+1] = P[i]==P[j]?j+1:0;
}
}
int main(){
int cas=1;
char ch;
while(~scanf("%d%*c",&n) && n){
printf("Test case #%d\n",cas++);
gets(T);
getFail(T,f);
for(int i=2; i<=n; ++i){
if(f[i]>0 && i%(i-f[i])==0){
printf("%d %d\n",i,i/(i-f[i]));
}
}
puts("");
}
return 0;
}