2020-2021:teams:legal_string:王智彪:ac自动机
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:ac自动机 [2021/07/23 23:35] 王智彪 |
2020-2021:teams:legal_string:王智彪:ac自动机 [2021/07/24 11:14] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 256: | 行 256: | ||
| for(int i=1;i<=t;i++) { | for(int i=1;i<=t;i++) { | ||
| printf("%d\n",AC.num[AC.ipos[mp[i]]]); | printf("%d\n",AC.num[AC.ipos[mp[i]]]); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | ===== 代码练习 ===== | ||
| + | |||
| + | 1.[[https://www.luogu.com.cn/problem/P3041]] | ||
| + | |||
| + | ==== 题目大意 ==== | ||
| + | |||
| + | 给定 $n$ 个字符串和一个长度 $k$ ，让求一个字符串长度为此长度，且这些字符串在这个字符串中出现次数之和最大。 $n≤20,k≤10^{3},$，这些字符串长度均不超过 $15$ 。所有字符串只含有 $A,B,C$ 。 | ||
| + | |||
| + | ==== 题目解析 ==== | ||
| + | |||
| + | 显然是个 $dp$ 。如果设 $dp[i][j]$表示长度到 $i$ ，后十五个字符为状态 $j$ （状压一下）的最大个数。这样复杂度是爆炸的，这些状态里有很多是不合适的，有很多是血亏的，其实我们只需要这些字符串中某些字符串的后缀往下走就好了，所以考虑 $AC$ 自动机。这样我们第二维其实就是所有字符串的状态节点数，这个节点数是不会超过 $300$ 的。 | ||
| + | |||
| + | 然后是 $dp$ 的转移， $dp[i][ch[j][k]]=max(dp[i][ch[j][k]],dp[i-1][j]+val[ch[j][k]])$ ，那么问题在于怎么计算 $val$ 数组。这个数组代表我到了这个结点，有多少个字符串新出现了，首先，以这个点为结尾的字符串数要算上，之后，对于跳 $fail$ 结点，显然也可以算到这个里面，所以有 $val[u]=val[fail[u]]+cnt[u]$ ，其中 $cnt[u]$ 是字符串们在这个点出现了多少次，这个插入的时候可以算。这里我们在 $BFS$ 的时候进行计算，这样失配点的答案已经是正确的，所以当前点的答案也是正确的。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | #define maxn 20200 | ||
| + | int mp[maxn]; | ||
| + | struct Trie { | ||
| + | int root,size,maxv,nxt[maxn][3],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<3; 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[nu]=len; | ||
| + | cnt[now_node]++; | ||
| + | } | ||
| + | void build_Trie() { | ||
| + | queue <int> q_trie; | ||
| + | fail[root]=root; | ||
| + | for(int i=0; i<3; 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<3; 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 dp[2021][321],ans,n; | ||
| + | int main() { | ||
| + | int t; | ||
| + | scanf("%d %d",&t,&n); | ||
| + | AC.init(); | ||
| + | for(int i=1; i<=t; i++) { | ||
| + | scanf("%s",str); | ||
| + | AC.insert2(str,i); | ||
| + | } | ||
| + | AC.build_Trie(); | ||
| + | memset(dp,0xaf,sizeof(dp)); | ||
| + | dp[0][0]=0; | ||
| + | for(int i=1;i<=n;i++) { | ||
| + | for(int j=0;j<AC.size;j++) { | ||
| + | for(int k=0;k<3;k++) { | ||
| + | dp[i][AC.nxt[j][k]] = max(dp[i][AC.nxt[j][k]],dp[i-1][j]+AC.val[AC.nxt[j][k]]); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | for(int i=0;i<AC.size;i++) { | ||
| + | if(dp[n][i]>=ans) ans=dp[n][i]; | ||
| + | } | ||
| + | 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自动机.1627054509.txt.gz · 最后更改: 2021/07/23 23:35 由 王智彪
