1.hash字符串

例题：POJ-1200:http://poj.org/problem?id=1200
题意：寻找存在nc个字符的字符串中给定字符串中不同子串数量
注：若无特殊规定，则nc应取131或13331以减少冲突
算法思想：将字符串拆分成含有n个字符的子串并将其转化为nc进制数。
字符串相同hash值一定相同，反之不成立（所以要减少冲突）
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10;
char str[N];
const int maxn=16e6+10;
bool hash[maxn];
int c[128];
int n,nc;
int main(){
    while(cin>>n>>nc>>str){
        memset(hash,false,sizeof(hash));//初始化
        memset(c,0,sizeof(c));
        int len=strlen(str)-n+1;//存在的最大可能组数
        int ans=len;
        int k=0;
        for(int i=0;i<len;i++){//字符与数字对应 
            if(c[str[i]-'a']==0) c[str[i]-'a']=k++;
            if(k==nc) break; //所有字符存在
        }
        for(int i=0;i<len;i++){//每n个字符所形成数字的值与其他是否相同 
            int num=0;
            for(int j=i;j<i+n;j++) num=num*nc+c[str[j]-'a'];//nc进制所表示数值
            num%=maxn;
            if(hash[num]) ans--;//相同则减去 
            else hash[num]=true;
                cout<<ans<<endl;
            }
    }    
    return 0;
}

2.最大最小表示法

字符串同构问题

int getmin(char p[]){
    int plen=strlen(p);
    int i=0,j=1,k=0;    //从i开始k长度和从j开始k长度的字符串相同(i,j表示当前判断的位置)
    while(i<plen&&j<plen&&k<plen){
        int t=p[(i+k)%plen]-p[(j+k)%plen]; //计算相对应位置上两个字符字典序大小 
        if(t==0) k++;
        else{
            if(t>0) i+=k+1;//i开头和j开头的有k个相同的字符    -->最大i,j颠倒
            else j+=k+1;
            if(i==j) j++;
            k=0;
        }        
    }
    return min(i,j);//较小的值就是我们最终开始的位置
}

3.对kmp的next[]数组的探索

例题：http://poj.org/problem?id=1961
题意：寻找字符串前缀的循环串，并输出为循环串时的位置和循环周期
公式：len%(len-next[i])==0,len/(len-next[i]);
参考博客：https://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html
注：在getnextval()函数内边判断边输出

while(j<plen){
        //p[k]为前缀，p[j]位后缀
        if(k==-1||p[k]==p[j]){
            j++;
            k++;
            if(j%(j-k)==0&&j/(j-k)>1)    //k=next[j]
              printf("%d %d\n",j,j/(j-k));//从字符串的第二个开始，看前面是循环串吗，是的话就输出此时的位置，和循环串的周期，周期必须大于1
            if(p[j]!=p[k]) next[j]=k;
            else next[j]=next[k];
        }
        else k=nex[k];
}

最大最小表示法+kmp()

例题：HDU-3374:http://acm.hdu.edu.cn/showproblem.php?pid=3374

4.扩展kmp

1.next[]代码：next[i]表示T[i,m-1]和T的最长公共前缀长度

void getnext(char *str)
{
    int i=0,j,p,len=strlen(str);
    next[0]=len;//初始化next[0]
    while(str[i]==str[i+1]&&i+1<len)//计算next[1]
    i++;
    next[1]=i;
    p=1;//初始化p的位置
    for(i=2;i<len;i++)
    {
        if(next[i-p]+i<next[p]+p)//第一种情况，可以直接得到next[i]的值
        next[i]=next[i-p];
        else//第二种情况，要继续匹配才能得到next[i]的值
        {
            j=next[p]+p-i;
            if(j<0)j=0;//如果i>p+next[p],则要从头开始匹配
            while(i+j<len&&str[j]==str[j+i])//计算next[i]
            j++;
            next[i]=j;
            p=i;//更新p的位置
        }
    }
}

2.extend[]代码：extend[i]表示T与S[i,n-1]的最长公共前缀

代码：

void exkmp(char *s1,char *s2)
{
    int i=0,j,p,len=strlen(s1),l2=strlen(s2);
    getnext(s2);//计算子串的next数组
    while(s1[i]==s2[i]&&i<l2&&i<len)//计算extend[0]
    i++;
    extend[0]=i;
    p=0;//初始化p的位置
    for(i=1;i<len;i++)
    {
        if(next[i-p]+i<extend[p]+p)//第一种情况，直接可以得到ex[i]的值
        extend[i]=next[i-p];
        else//第二种情况，要继续匹配才能得到extend[i]的值
        {
            j=extend[p]+p-i;
            if(j<0)j=0;//如果i>extend[p]+p则要从头开始匹配
            while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算extend[i]
            j++;
            extend[i]=j;
            po=i;//更新po的位置
        }
    }
}

例题：HDU-6629:http://acm.hdu.edu.cn/showproblem.php?pid=6629