Logue P3796: AC automaton template (enhanced)

2020.6.13
This paper borrows @ hyfhaha's idea of problem solving.

The day before yesterday, I went back to school to see my teacher. They were all the same. They didn't change at all. The teacher was also very happy to see us. He left us to study at night and then let us go. A-Level class asked cs about the preparation work. I also made a small profit in noip. Hee hee, I hope I can make some preparation for my younger brother and younger sister. This year's trend is not very good. It's really sad to see Mr. Tan worried about the next term. On the one hand, it's the general environment. On the other hand, the admission results of the 7th middle school are a little unsatisfactory since our session. Although there are several 20-30 students in this session, half of our class went to the top 30 universities in the United States. Without the top 30 majors, they are also the top majors. Fang's bu bioengineering, wsl's art college, and lyx's animal medicine are all top majors. Unfortunately, teachers often say that we will never see any more students like us after the 18th graduation, maybe it's related to institutions, maybe it's related to people. There are not a few people like me who come in that year, maybe it's related to the declining sat score. I don't know why, or I hope that the school can meet the next brilliant period and have better results It makes more sense to quit.

ac automata, the white board idea of this problem is violent matching, but when I see 1e6, multiple sets of data, I think it's 100% overtime, and then someone tells me that this can be operated on the fail tree, but I still don't think of it. After reading the solution of the question, we know that we can match and do it at the same time. That is to say, each trie[cur][val] has a unique substring to determine the subscript, so if b is included in the path when matching a, b must be a substring. As long as the ending node of trie represented by the subscript is marked with subscript, it can be added directly when matching. It's a very clever way. Originally I wanted to use char array, but I found that it can't be opened. I'd better use str.
code:

#include <bits/stdc++.h>
using namespace std;
#define limit (500000 + 5)//Prevent spillage
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//One step, two steps
#define EPS 1e-6
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(int i = a; i <= b ; ++i)
#define per(i, a, b) for(int i = b ; i >= a ; --i)
#define mint(a,b,c) min(min(a,b), c)
#define MOD 998244353
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin)
typedef long long ll;
typedef unsigned long long ull;
ll read(){
    ll sign = 1, x = 0;char s = getchar();
    while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}
    while(s >= '0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}
    return x * sign;
}//Fast reading
void write(ll x){
    if(x < 0) putchar('-'),x = -x;
    if(x / 10) write(x / 10);
    putchar(x % 10 + '0');
}
int n,num[limit];

int ans[limit];
struct node{
    #define ALPHA 25
    int trie[limit][26], fail[limit],tot = 0;
    void clear(){
        memset(trie, 0 , sizeof(trie));
        memset(fail, 0 , sizeof(fail));
        memset(num, 0 , sizeof(num));
        memset(ans, 0 , sizeof(ans));
        tot = 0;
    }
    void insert(const char *s, int index){
        int root = 0;
        int len = strlen(s);
        rep(i , 0 ,len - 1){
            int val = s[i] - 'a';
            if(!trie[root][val])trie[root][val] = ++tot;//Not visited
            root = trie[root][val];
        }
        num[root] = index;
    }
    void build(){
        queue<int>q;
        rep(i ,0 , ALPHA){
            if(trie[0][i])fail[trie[0][i]] = 0, q.push(trie[0][i]);
        }
        while (q.size()){
            int u = q.front();
            q.pop();
            rep(i , 0 ,ALPHA){
                if(trie[u][i]){
                    fail[trie[u][i]] = trie[fail[u]][i];
                    q.push(trie[u][i]);
                }else{
                    trie[u][i] = trie[fail[u]][i];
                }
            }
        }
    }
    void operator[](const char * s){
        int len = strlen(s);
        int root = 0 ;
        rep(i, 0 , len - 1){
            root = trie[root][s[i] - 'a'];
            for(int t = root; t ; t = fail[t]){
                ++ans[num[t]];
            }
        }
    }
};
string str;
string collection[limit];
node AC_Automaton;//name
int main() {
#ifdef LOCAL
    FOPEN;
#endif
    while(cin>>n && n){
        rep(i ,1, n){
            cin>>str;
            collection[i] = str;
            AC_Automaton.insert(str.c_str(), i);
        }
        int maxx = 0;
        cin>>str;
        AC_Automaton.build();
        AC_Automaton[str.c_str()];
        rep(i ,1, n){
            maxx = max(maxx, ans[i]);
        }
        write(maxx),putchar('\n');
        rep(i,1,n){
            if(ans[i] == maxx){
                cout<<collection[i]<<endl;
            }
        }
        AC_Automaton.clear();
    }

    return 0;
}

Keywords: Session iOS

Added by iamtom on Sat, 13 Jun 2020 07:40:35 +0300