2020-2021:teams:legal_string:王智彪:ac自动机
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:王智彪:ac自动机 [2021/07/24 01:49] 王智彪 |
2020-2021:teams:legal_string:王智彪:ac自动机 [2021/07/24 11:14] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 369: | 行 369: | ||
| } | } | ||
| printf("%d\n",ans); | printf("%d\n",ans); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | 2.[[https://www.luogu.com.cn/problem/P3121]] | ||
| + | |||
| + | ==== 题目大意 ==== | ||
| + | |||
| + | 给定一个长度不超过 $10^{5}$ 的字符串，又给了 $n$ 个单词记为 $t_{1},t_{2},……,t_{n}$ 。每次删除在大字符串中出现最早的列表中的单词，然后拼接，直到不能再删，保证列表中单词不会出现一个单词是另一个单词子串的情况，让输出最后的字符串。 | ||
| + | |||
| + | ==== 题目解析 ==== | ||
| + | |||
| + | 建立 $AC$ 自动机，遇到某个字符串的结尾，就删掉，用一个栈存有哪些字符还留着，删的时候一直弹栈，然后跳到栈顶代表的结点就行了，最后输出栈中所有字符即可。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | #define maxn 202000 | ||
| + | int mp[maxn]; | ||
| + | struct Trie { | ||
| + | int root,size,maxv,nxt[maxn][26],fail[maxn],vis[maxn],pos[maxn],L[maxn],last[maxn],num[maxn],ipos[maxn],val[maxn],cnt[maxn]; | ||
| + | int new_node() { | ||
| + | for(int i=0; i<26; i++) nxt[size][i]=-1; | ||
| + | size++; | ||
| + | //end[size++]=0; | ||
| + | return size-1; | ||
| + | } | ||
| + | void init() { | ||
| + | for(int i=0; i<=size; i++) { | ||
| + | vis[i]=0,pos[i]=0;//end[i]=0; | ||
| + | } | ||
| + | maxv=0; | ||
| + | size=0; | ||
| + | root=new_node(); | ||
| + | } | ||
| + | void insert2(char tmp[],int nu) { | ||
| + | int len=strlen(tmp),now_node=root; | ||
| + | for(int i=0; i<len; i++) { | ||
| + | if(nxt[now_node][tmp[i]-'a']==-1) nxt[now_node][tmp[i]-'a']=new_node(); | ||
| + | now_node=nxt[now_node][tmp[i]-'a']; | ||
| + | } | ||
| + | if(!pos[now_node]) { | ||
| + | pos[now_node]=nu; | ||
| + | mp[nu]=nu; | ||
| + | ipos[nu]=now_node; | ||
| + | } else { | ||
| + | mp[nu]=mp[pos[now_node]]; | ||
| + | ipos[nu]=now_node; | ||
| + | } | ||
| + | L[now_node]=len; | ||
| + | cnt[now_node]++; | ||
| + | } | ||
| + | void build_Trie() { | ||
| + | queue <int> q_trie; | ||
| + | fail[root]=root; | ||
| + | for(int i=0; i<26; i++) { | ||
| + | if(!(~nxt[root][i])) nxt[root][i]=root; | ||
| + | else { | ||
| + | fail[nxt[root][i]]=root; | ||
| + | q_trie.push(nxt[root][i]); | ||
| + | } | ||
| + | } | ||
| + | while(!q_trie.empty()) { | ||
| + | int now_node=q_trie.front(); | ||
| + | q_trie.pop(); | ||
| + | for(int i=0; i<26; i++) { | ||
| + | if(!(~nxt[now_node][i])) nxt[now_node][i]=nxt[fail[now_node]][i]; | ||
| + | else { | ||
| + | fail[nxt[now_node][i]]=nxt[fail[now_node]][i]; | ||
| + | q_trie.push(nxt[now_node][i]); | ||
| + | } | ||
| + | } | ||
| + | val[now_node]=val[fail[now_node]]+cnt[now_node]; | ||
| + | } | ||
| + | } | ||
| + | } AC; | ||
| + | char str[maxn]; | ||
| + | char str1[maxn]; | ||
| + | int n,pos[maxn]; | ||
| + | stack<int> sta; | ||
| + | vector<int> vv; | ||
| + | int main() { | ||
| + | int t; | ||
| + | scanf("%s",&str); | ||
| + | int len=strlen(str); | ||
| + | AC.init(); | ||
| + | scanf("%d",&n); | ||
| + | for(int i=1;i<=n;i++) { | ||
| + | scanf("%s",str1); | ||
| + | AC.insert2(str1,i); | ||
| + | } | ||
| + | AC.build_Trie(); | ||
| + | int now_node=AC.root; | ||
| + | for(int i=0;i<len;i++) { | ||
| + | now_node=AC.nxt[now_node][str[i]-'a']; | ||
| + | pos[i]=now_node; | ||
| + | sta.push(i); | ||
| + | if(AC.L[now_node]) { | ||
| + | for(int j=0;j<AC.L[now_node];j++) { | ||
| + | sta.pop(); | ||
| + | } | ||
| + | if(!sta.empty()) now_node=pos[sta.top()]; | ||
| + | else now_node=AC.root; | ||
| + | } | ||
| + | //printf("%d %d\n",i,sta.size()); | ||
| + | } | ||
| + | while(!sta.empty()) { | ||
| + | vv.push_back(sta.top()); | ||
| + | sta.pop(); | ||
| + | } | ||
| + | for(int i=vv.size()-1;i>=0;i--) { | ||
| + | printf("%c",str[vv[i]]); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/王智彪/ac自动机.1627062570.txt.gz · 最后更改: 2021/07/24 01:49 由 王智彪
