样例全过 Wa On #3 求调
查看原帖
样例全过 Wa On #3 求调
762646
Piggy343288楼主2023/9/4 15:03
#include<bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 10, maxS = 505;
char A[maxS][maxS];
int n, m, q;
vector<int> g[maxN];

struct AC_Automaton {
    int ch[maxN][26], fail[maxN], pos[maxN], cnt, ans[maxN];
    int insert(string s) {
        int cur = 0;
        for(char i: s) {
            int c = i - 'A';
            if(!ch[cur][c]) ch[cur][c] = ++cnt;
            cur = ch[cur][c];
        }
        return cur;
    }
    void build() {
        queue<int> q;
        for(int i = 0; i < 26; i++) { if(ch[0][i]) fail[ch[0][i]] = 0, q.push(ch[0][i]); }
        while(!q.empty()) {
            int c = q.front(); q.pop();
            for(int i = 0; i < 26; i++) {
                if(ch[c][i]) fail[ch[c][i]] = ch[fail[c]][i], q.push(ch[c][i]);
                else ch[c][i] = ch[fail[c]][i];
            }
        }
    }
    void query(string s, int op) {
        int cur = 0;
        for(char i : s) {
            cur = ch[cur][i - 'A'];
            ans[cur] += op;
        }
    }
    void dfs(int u) {
        for(int i: g[u]) {
            dfs(i); ans[u] += ans[i];
        }
    }    
} ac;

string work(int a, int b, int c, int d) {
    string s;
    for(int i = b; i <= d; i++) s += A[a][i];
    for(int i = a + 1; i <= c; i++) s += A[i][d];
    return s;
}

int main() {
    string s; cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> (A[i] + 1);
    for(int i = 1; i <= q; i++) {
        cin >> s;
        ac.pos[i] = ac.insert(s);
    }
    ac.build();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ac.query(work(i, 1, n, j), 1);
            ac.query(work(i, 1, i, j - 1), -1);
            ac.query(work(i + 1, j, n, j), -1);
        }
    }
    for(int i = 1; i <= ac.cnt; i++) g[ac.fail[i]].push_back(i);
    ac.dfs(0);
    for(int i = 1; i <= q; i++) cout << ac.ans[ac.pos[i]] << "\n";
}
2023/9/4 15:03
加载中...