欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AC自动机

程序员文章站 2022-06-06 17:43:37
...

刚学 ac自动机,其实就是Tire的扩展,外加一个 fail指针,避免每次从树根遍历,fail指针指向当前字符串最长的后缀。看图吧
两个字符串:
abc
bc
建完字典树之后:
AC自动机
加入fail指针:
AC自动机
AC自动机
AC自动机
AC自动机
没有后缀的话 指向根节点,比如 abc c的fail指针我们先找 bc 没有的话 找c 还没有的话就指向根

加个题
HDU 2222

#include <bits/stdc++.h>
using namespace std;
const int Max_P = 500005;
struct AC{
    int size;
    struct node
    {
        int next[26];
        int fail, cnt;
    }stateTable[Max_P];

    void init(){//初始化
        size = 1;
        for(int i = 0; i < Max_P; i ++){
            memset(stateTable[i].next, 0 , sizeof stateTable[i].next);
            stateTable[i].fail = stateTable[i].cnt = 0;
        }
    }

    void build(){//构建fail树,bfs()
        stateTable[0].fail = -1;
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i = 0; i < 26;i ++){
                if(stateTable[x].next[i]){
                    if(x == 0) stateTable[stateTable[x].next[i]].fail = 0;
                    else {
                        int v = stateTable[x].fail;
                        while(v != -1){
                            if(stateTable[v].next[i]){
                                stateTable[stateTable[x].next[i]].fail = stateTable[v].next[i];
                                break;
                            }
                            v = stateTable[v].fail;
                        }
                        if(v == -1) stateTable[stateTable[x].next[i]].fail = 0;
                    }
                    q.push(stateTable[x].next[i]);
                }
            }
        }
    }
    void insert(char *S){//建立字典树
        int len = strlen(S);
        int now = 0;
        for(int i = 0; i < len; i ++){
            if(!stateTable[now].next[S[i] - 'a']) stateTable[now].next[S[i] - 'a'] = size ++;
            now = stateTable[now].next[S[i] - 'a'];
        }
        stateTable[now].cnt ++;
    }
    int Get(int x){
        int res = 0;
        while(x){
            res = res + stateTable[x].cnt;
            stateTable[x].cnt = 0;//看题意是否需要置零
            x = stateTable[x].fail;
        }
        return res;
    }
    int match(char *S){//模式串匹配
        int len = strlen(S);
        int now = 0;
        int res = 0;
        for(int i = 0 ;i < len; i ++){
            if(stateTable[now].next[S[i] - 'a']){
                now = stateTable[now].next[S[i] - 'a'];
            }
            else{
                int v = stateTable[now].fail;
                while(v != -1 && !stateTable[v].next[S[i] - 'a']) v = stateTable[v].fail;
                if(v == -1) now = 0;
                else {
                    now = stateTable[v].next[S[i] - 'a'];
                }
            }
            if(stateTable[now].cnt)//获得答案,当前如果是一个前缀就加入
                res += Get(now);
        }
        return res;
    }
}ans;

char S[1000006];
int main()
{
    int t;
    cin >> t;
    while(t --){
        int n;
        scanf("%d",&n);
        ans.init();
        for(int i = 0; i < n; i ++){
            scanf("%s",S);
            ans.insert(S);
        }
        ans.build();
        scanf("%s",S);
        printf("%d\n",ans.match(S));
    }
}

第二个题

fail树的应用有点类似拓扑的样子,如果 i 是 j 的后缀,那么j的 fail 指针会跳回到i,那么i.cnt= i .cnt + j.cnt, 同时记录一下 i 在其他串中充当前缀的次数

#include <bits/stdc++.h>
using namespace std;
const int Max_P = 500005;
queue<int> p;
struct AC{
	int size;
	int num[1000006];
	int len1 = 0;
	struct node
	{
		int next[26];
		int fail, cnt;
	}stateTable[1000006];

	void init(){
		size = 1;
		for(int i = 0; i < 1000006; i ++){
			memset(stateTable[i].next, 0 , sizeof stateTable[i].next);
			stateTable[i].fail = stateTable[i].cnt = 0;
		}
	}

	void build(){
		stateTable[0].fail = -1;
		queue<int> q;
		q.push(0);

		while(!q.empty()){
			int x = q.front();
			q.pop();
			num[++len1] = x;
			for(int i = 0; i < 26;i ++){
				if(stateTable[x].next[i]){
					if(x == 0) stateTable[stateTable[x].next[i]].fail = 0;
					else {
						int v = stateTable[x].fail;
						while(v != -1){
							if(stateTable[v].next[i]){
								stateTable[stateTable[x].next[i]].fail = stateTable[v].next[i];
								break;
							}
							v = stateTable[v].fail;
						}
						if(v == -1) stateTable[stateTable[x].next[i]].fail = 0;
					}
					q.push(stateTable[x].next[i]);
				}
			}
		}
		for(int i = len1; i >= 1; i --){
			stateTable[stateTable[num[i]].fail].cnt+= stateTable[num[i]].cnt;
		}
	}
	void insert(char *S){
		int len = strlen(S);
		int now = 0;
		for(int i = 0; i < len; i ++){
			if(!stateTable[now].next[S[i] - 'a']) stateTable[now].next[S[i] - 'a'] = size ++;
			now = stateTable[now].next[S[i] - 'a'];
			stateTable[now].cnt ++;
		}
		p.push(now);
	}
}ans;

char S[1000006];
int main()
{
	int n;
	scanf("%d",&n);
	ans.init();
	for(int i = 0; i < n; i ++){
		scanf("%s",S);
		ans.insert(S);
	}
	ans.build();
	
	while(!p.empty()){
		cout << ans.stateTable[p.front()].cnt << endl;
		p.pop();
	}
	
}
相关标签: 字符串