KMP与AC自动机

KMP算法主要思想就是预处理出失配函数, 从而减少匹配失败时的回溯, 复杂度是$\Theta(m+n)$, 已达到理论下界

c++代码如下

 

int n, f[N];
char t[N], p[N];

void getFail(char *s) {
	int n = strlen(s);
	f[0]=f[1]=0;
	REP(i,1,n-1) {
		int j = f[i];
		while (j&&s[i]!=s[j]) j=f[j];
		f[i+1] = s[i]==s[j]?j+1:0;
	}
}


int main() {
	scanf("%s%s", t, p);
	getFail(p);
	int now = 0, n = strlen(t), m = strlen(p);
	REP(i,0,n-1) {
		while (now&&p[now]!=t[i]) now=f[now];
		if (p[now]==t[i]) ++now;
		if (now==m) printf("%d\n",i-m+1);
	}
}

 

 

AC自动机就是把kmp的链状结构变成树状结构了, 变为在trie上跑bfs

 

void getFail() {
    queue<int> q;
    f[0] = 0;
    for (int c=0; c<SZ; ++c) {
        int u = ch[0][c];
        if (u) f[u]=0,q.push(u),last[u]=0;
    }   
    while (!q.empty()) {
        int r = q.front(); q.pop();
        for (int c=0; c<SZ; ++c) {
            int u = ch[r][c];
            if (!u) ch[r][c]=ch[f[r][c]];
            else { 
                q.push(u);
                int v = f[r];
                while (v&&!ch[v][c]) v=f[v];
                f[u] = ch[f[r]][c];
                last[u] = val[f[u]]?f[u]:last[f[u]];
            }   
        }   
    }
}