题意 : 给出 n 个串、然后给出一个问询串、问你对于问询串的每一个前缀、需要至少补充多少单词才能使得其后缀包含 n 个串中的其中一个、注意 '-' 字符代表退格
分析 :
多串的匹配问询自然想到 AC 自动机 或者 构建 Trie 图
首先将 N 个串丢到 Trie 图里面
对于每一个节点记录其要变成一个完整的串最少需要补充的单词数
然后在问询的时候、由于有退格操作
于是需要将跑过的节点路径记录下来以便恢复
这个我们可以使用栈来做到
然后对于问询串的每一个前缀问询
可以采用 DP 的方式来一直记录跳 Fail 时候每个节点的最优值是什么
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scl(i) scanf("%lld", &i) #define scll(i, j) scanf("%lld %lld", &i, &j) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l) #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l) #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l) #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define VI vector<int> #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define VL vector<long long> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> #define _TIME 0 #define _INPUT 0 #define _OUTPUT 0 clock_t START, END; void __stTIME(); void __enTIME(); void __IOPUT(); using namespace std; const int max_node = 1e6 + 10; const int max_len = 1e5 + 10; const int Letter = 26; struct Aho{ struct StateTable{ int nxt[Letter]; int fail, cnt, dis; bool vis; void init(){ memset(nxt, 0, sizeof(nxt)); fail = 0; cnt = 0; dis = 0x3f3f3f3f; vis = false; } }Node[max_node]; int sz; queue<int> que; inline void init(){ while(!que.empty())que.pop(); Node[0].init(); sz = 1; } inline void insert(char *s, int len){ int now = 0; Node[now].dis = min(Node[now].dis, len); for(int i=0; i<len; i++){ int idx = s[i] - 'a'; if(!Node[now].nxt[idx]){ Node[sz].init(); Node[now].nxt[idx] = sz++; } now = Node[now].nxt[idx]; Node[now].dis = min(Node[now].dis, len-i-1); } Node[now].cnt++; } inline void build(){ Node[0].fail = -1; que.push(0); while(!que.empty()){ int top = que.front(); que.pop(); for(int i=0; i<Letter; i++){ if(Node[top].nxt[i]){ if(top == 0) Node[ Node[top].nxt[i] ].fail = 0; else{ int v = Node[top].fail; while(v != -1){ if(Node[v].nxt[i]){ Node[ Node[top].nxt[i] ].fail = Node[v].nxt[i]; break; }v = Node[v].fail; }if(v == -1) Node[ Node[top].nxt[i] ].fail = 0; }que.push(Node[top].nxt[i]); }else Node[top].nxt[i] = top!=0?Node[ Node[top].fail ].nxt[i]:0; } } } // int Match(char *s){ // int now = 0, res = 0; // for(int i=0; s[i]!=' '; i++){ // int idx = s[i] - 'a'; // now = Node[now].nxt[idx]; // int tmp = now; // while(tmp != 0){ // res += Node[tmp].cnt; // Node[tmp].cnt = 0; // tmp = Node[tmp].fail; // } // } // return res; // } int dp[max_node]; int GetDP(int cur){ if(cur == 0) return Node[cur].dis; if(dp[cur] != -1) return dp[cur]; dp[cur] = min(Node[cur].dis, GetDP(Node[cur].fail)); return dp[cur]; } void query(char *s, int len){ int now = 0; memset(dp, -1, sizeof(dp)); stack<int> pos; printf("%d ", Node[now].dis); for(int i=0; i<len; i++){ if(s[i] == '-'){ if(!pos.empty()) pos.pop(); if(pos.empty()) now = 0; else now = pos.top(); }else{ int idx = s[i] - 'a'; now = Node[now].nxt[idx]; pos.push(now); } int ans = Node[now].dis; ans = min(ans, GetDP(now)); printf("%d ", ans); } } }ac; char s[max_len]; int main(void){__stTIME();__IOPUT(); int n; sci(n); ac.init(); for(int i=0; i<n; i++){ scs(s); ac.insert(s, strlen(s)); } ac.build(); scs(s); ac.query(s, strlen(s)); __enTIME();return 0;} void __stTIME() { #if _TIME START = clock(); #endif } void __enTIME() { #if _TIME END = clock(); cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl; #endif } void __IOPUT() { #if _INPUT freopen("in.txt", "r", stdin); #endif #if _OUTPUT freopen("out.txt", "w", stdout); #endif }