总结

1.kmp

kmp是一种字符串匹配的算法,普通的字符串匹配需要时间O(n*m) 。n:字符串长度 m:模版串长度,kmp算法通过对模版串进行预处理来找到每个位置的后缀和第一个字母的前缀的最大公共长度,可以让复制度降低到O(n+m)。

下面为kmp的模板

#include<bits/stdc++.h>
using namespace std;
?
const int N = 1e6+10;
int nxt[N];
int n,m;
int s[N];
int t[N];
?
void getnxt()   //求子串的next数组 最大前后缀 
{
    int i=1;
    int j=0;
    memset(nxt,0,sizeof(nxt));
    while(i<m) {   //当然在未出现相等之前都nxt都赋予0 
        if(t[j]==t[i]) { //j是第一位 ，i从第二位开始 ，如果相等了，说明出现了相同前后缀 
            nxt[i] = ++j;   //然后开始next数组  先记录i，然后i，j都++  
            i++;        //第i位若相等的话就应该是已经存在相同前后缀了，故先+1->++j; 
        }
        else if(!j)  { //j=0，i++往后挪 
            i++; //当有一次相等的话，该条件就不会存在了
        }       
        else {                  // 123124   eg： 此时到a[5]  nxt[4]=2 检索a[5]时 i=5 j=2 nxt[j-1]=0，j=0; 
            j=nxt[j-1];   //若是不相等的话       j返回到前缀的最后一个相等的nxt值 即123124 返回的是a[1] 的nxt值 
        }
    }
}  
?
int kmp()
{
    int i=0;
    int j=0;
    while(i<n&&j<m) {         //对子母 进行检索 
        if(s[i] == t[j]) {
            i++;
            j++;
        }    //若都相等的话都向后挪 ++ 
        else if(!j) {
            i++;
        }
        else {
            j = nxt[j-1];
        }           //类同于求nxt 
    }
    if(j == m) 
        return i-m+1;       //若到最后能够遍历到j  则在母串中的位置为i-m+1 
    else 
        return -1;      //否则返回-1 
}
?
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; i++){
            scanf("%d",&s[i]);
        }
        for(int i = 0; i < m; i++) {
            scanf("%d",&t[i]);
        }
        getnxt();
        printf("%d\n",kmp());
        
?
```
}
return 0;
```
?
}

2.哈希算法

例如：poj1200

hash算法很强，具体就是，把原串中的每个字符给它赋值，用数字来代替不同的字母，比如a可以用0表示，b可以用1表示，等等。

然后再遍历长度为n的子串，把每个子串用刚才赋值的数字按10进制或者m进制转化成一个数（其实就是把长度为n的那一小段字符表示成一个数），可以想象，只要子串不同，那表示出来的数字结果就一定不相同，这就把字符串和数字构成了一一对应关系，进而也就能用不同的数字表示不同的子串，最后只要遍历一下不同的数字有多少，就是答案了

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 16000000+10;
int m,n;
char str[N];
int hash[N];
int vis[500];
 
int main()
{
    while(~scanf("%d%d%s",&m,&n,str)) {
        int num = 0,ans = 0;
        int len=strlen(str);
        memset(vis,0,sizeof(vis));
        vis[0] = num++;
        for(int i = 1; i < len; i++) {
            if(vis[str[i]] == 0)
                vis[str[i]] = num++;
        }
        for(int i = 0; i <= len-m; i++) {
            int sum = 0;
            for(int j = 0; j < m;j++) {
                sum = sum*num + vis[str[i+j]];
            }
            if(!hash[sum]) {
                hash[sum]=1;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

3.最大最小表示法

迷迷糊糊没怎么弄懂，先把模板放这儿，有空再回来看看

hdu3374

#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int nex[N], l;
char s[N];
 
void getNext()
{
    int i = 0, j = nex[0] = -1;
    while(i < l)
    {
        if(j == -1 || s[i] == s[j])
            nex[++i] = ++j;
        else j = nex[j];
    }
}
 
int getPos(bool op) //op = 0最小表示法  op = 1 最大表示法
{
    strncpy(s + l, s, l);
    int i = 0, j = 1;
    while(i < l && j < l)
    {
        int k = 0;
        while(k < l && s[i + k] == s[j + k]) ++k;
        if(k >= l) break;
        if((s[i + k] > s[j + k]) ^ op) i += k + 1;
        else j += k + 1;
        if(i == j) ++j;  //保证i != j
    }
    return i < j ? i : j;
}
 
int main()
{
    while(~scanf("%s", s))
    {
        l = strlen(s);
        getNext();
        int rl = l - nex[l], t = l % rl ? 1 : l / rl;
        int p0 = getPos(0) + 1, p1 = getPos(1) + 1;
        printf("%d %d %d %d\n", p0, t, p1, t);
    }
    return 0;
}

4.poj1961

这道题比较水，只要知道循环节的公式就能求出来，就是用kmp里面的next数组，然后加上循环节的

公式就可以出来结果。主要是记住这个公式。

#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ne[1000005];
char mo[1000005];   
void nex(char *mo)
{
    int i = 0,j = -1;
    ne[0]=-1;
    while(mo[i]) {
        while(j!=-1&&mo[j]!=mo[i])
            j=ne[j];
        ne[++i]=++j;
    }
}
?
int main()
{
    int n;
    int t = 0;
    while(1) {
        scanf("%d",&n);
        if(n == 0) {
            break;
        }
        scanf("%s",mo);
        nex(mo);
        printf("Test case #%d\n",++t);
        for(int i=2; i<=n; ++i)
        {
            if(i%(i-ne[i])==0 && ne[i]!=0)
                printf("%d %d\n",i,i/(i-ne[i]));
        }
        printf("\n");
    }
    return 0;
}

5.ac自动机

待续

字符串总结（未完待续）

原文：https://www.cnblogs.com/clb123/p/11512555.html