[笔记-字符串问题] 字符串基础都不是

[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher
[NWPU][2018暑假集训]day13

模版

KMP算法

应用于单个模式串匹配，求最小循环节等
我的观点来看KMP的fail数组
就是值域和定义域都是串的长度，返回值是这个串能够匹配后缀的最大前缀串长度
但是纯循环节构成的串中，这个返回值不包括第一个循环节
比如aabaabaab
fail[9]6 fail[6]3

const int maxn=1e6+20, maxm=1e4+20;
char P[maxm], T[maxn];
int fail[maxm];
void getFail(int m){
    fail[0]=fail[1]=0;
    for (int i=1; i<m; i++){
        int j=fail[i];
        while (j && P[j]!=P[i]) j=fail[j];
        fail[i+1]=((P[i]==P[j])?j+1:0);
    }
}

int count(int n, int m){
    int cnt=0;
    getFail(m);
    for (int i=0, j=0; i<n; i++){
        while (j && T[i]!=P[j]) j=fail[j];
        if (P[j]==T[i]) j++;
        if (j==m){
            // cnt++; j=0; // 匹配成功。这里随便改，j是模式串下标，i是匹配串下标
        }
    }return cnt;
}

AC自动机

const int maxn=1000+20, maxw=50+20, maxl=2000000+20;
const int ACSize=maxn*maxw, maxitem=128;    // 注意此处ACSize最大的情况不超过 总词数*词长度，maxitem指分支数量，所有可见ASCII码个数128(in HDU)
struct ACauto{
    int next[ACSize][maxitem], fail[ACSize], cnt[ACSize];
    int root, total;
    int newnode(void){
        for(int pos=0; pos<maxitem; pos++)
            next[total][pos]=-1;
        cnt[total]=0;    // 词尾节点的初始化，不是词尾就赋0或-1
        return total++;
    }
    void init(void){
        total=0;
        root=newnode();
    }
    int getPos(char ch){
        return ch;
    }

    void insert(char buf[], int idx){
        int now=root;
        for(int i=0; buf[i]; i++){
            int pos=getPos(buf[i]);
            if(next[now][pos]==-1)
                next[now][pos]=newnode();
            now=next[now][pos];
        }
        cnt[now]=idx; // 这里维护词尾节点的值
    }

    void build(void){    // 一般不会改GetFail算法
        queue<int> que;
        fail[root]=root;
        for(int i=0; i<maxitem; i++)
            if(next[root][i]==-1)
                next[root][i]=root;
            else{
                fail[next[root][i]]=root;
                que.push(next[root][i]);
            }

        while(!que.empty()){
            int now=que.front(); que.pop();

            for(int pos=0; pos<maxitem; pos++)
                if(next[now][pos]==-1)
                    next[now][pos]=next[fail[now]][pos];
                else{
                    fail[next[now][pos]]=next[fail[now]][pos];
                    que.push(next[now][pos]);
                }
        }
    }

    void query(char buf[], int counter[]){
        int now=root;
        for(int i=0; buf[i]; i++){
            int pos=getPos(buf[i]);
            now=next[now][pos];
            for (int tmp=now; tmp!=root; tmp=fail[tmp]) if (cnt[tmp])
                counter[cnt[tmp]]++; // 匹配成功。这里随便改
        }
    }
}AC;

// 注意使用前AC.init()，插入后AC.build()