UVA - 11019 Matrix Matcher (AC自动机)

小灰灰 2022-05-17 02:15 93阅读 0赞

[传送门][Link 1]

思路：可以对于模式矩阵的每一行构造AC自动机，然后在目标矩阵的每一行找模式矩阵的每一行。如果找到了，就在（R-r， c）位置加一，R是目标矩阵的行，r是模式矩阵的行，c是R矩阵正在匹配行的列，这样只要最后遍历一边记数矩阵， 看看哪个点是模式矩阵的行数就行了，对于模式矩阵相同的行，在插入的时候我用了vector去保存。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e6+10;
    const int mo=998244353;
    const double eps=1e-4;
    int n, m, X, Y, cnt[1010][1010];
    char M1[1010][1010], M2[1010][1010];
    
    struct Trie{
        int nxt[N][26], fail[N], ed[N], root, L;
        vector<int> R[N];
        int newnode(){
            for(int i=0; i<26; i++)
                nxt[L][i]=-1;
            ed[L]=0;
            R[L].clear();
            return L++;
        }
    
        void init(){
            L=0;
            root=newnode();
        }
    
        void Insert(char buf[], int r){
            int now=root;
            for(int i=0; i<Y; i++){
                int to=buf[i]-'a';
                if(nxt[now][to]==-1)
                    nxt[now][to]=newnode();
                now=nxt[now][to];
            }
            ed[now]++;
            R[now].push_back(r);
        }
    
        void build(){
            queue<int> Q;
            int now=root;
            fail[now]=now;
            for(int i=0; i<26; i++){
                if(nxt[now][i]==-1)
                    nxt[now][i]=now;
                else{
                    fail[nxt[now][i]]=now;
                    Q.push(nxt[now][i]);
                }
            }
    
            while(!Q.empty()){
                now=Q.front();
                Q.pop();
                for(int i=0; i<26; i++)
                    if(nxt[now][i]==-1)
                        nxt[now][i]=nxt[fail[now]][i];
                    else{
                        fail[nxt[now][i]]=nxt[fail[now]][i];
                        Q.push(nxt[now][i]);
                    }
            }
        }
    
        void query(char buf[], int r){
            int now=root;
    
            for(int i=0; i<m; i++){
                int to=buf[i]-'a';
                now=nxt[now][to];
                int tmp=now;
                while(tmp!=root){
                    for(int j=0; j<ed[tmp]; j++)
                        if(r-R[tmp][j]>=0)
                            cnt[r-R[tmp][j]][i]++;
                    tmp=fail[tmp];
                }
            }
        }
        void debug(){
            for(int i=0; i<L; i++){
                printf("id = %3d, fail = %3d, end = %3d, chi = [", i, fail[i], ed[i]);
                for(int j=0; j<26; j++)
                    printf("%2d", nxt[i][j]);
                printf("]\n");
            }
        }
    }T;
    
    int main(){
            int t;
            scanf("%d", &t);
            while(t--){
                T.init();
                scanf("%d%d", &n, &m);
                for(int i=0; i<n; i++)for(int j=0; j<m; j++) cnt[i][j]=0;
                for(int i=0; i<n; i++){
                    scanf("%s", M1[i]);
                }
                scanf("%d%d", &X, &Y);
                for(int i=0; i<X; i++){
                    scanf("%s", M2[i]);
                    T.Insert(M2[i], i);
                }
                T.build();
                //T.debug();
                for(int i=0; i<n; i++)
                    T.query(M1[i], i);
                int ans=0;
                for(int i=0; i<n; i++)
                    for(int j=0; j<m; j++)
                        if(cnt[i][j]==X) ans++;
    
                printf("%d\n", ans);
            }
            return 0;
    }

[Link 1]: https://cn.vjudge.net/problem/UVA-11019