大型网站建设定制,wordpress 重写 函数,建设银行手机银行官方网站下载,邢台市信息产业集团有限公司正题
题目链接:https://www.luogu.com.cn/problem/P3041 题目大意
输入nnn个只有ABCABCABC的字符串#xff0c;求一个长度为LLL的字符串中最多包含多少个子串是nnn个字符串中的一个 解题思路
考虑ACACAC自动机是如何进行匹配的#xff0c;对于下一个字符#xff0c;如果有…正题
题目链接:https://www.luogu.com.cn/problem/P3041 题目大意
输入nnn个只有ABCABCABC的字符串求一个长度为LLL的字符串中最多包含多少个子串是nnn个字符串中的一个 解题思路
考虑ACACAC自动机是如何进行匹配的对于下一个字符如果有路便往那个方向走去然后统计该点沿条failfailfail到根节点所经过所有节点的值。然后如果没有继续往下走的路了就跳到该节点的failfailfail继续走因为在求failfailfail的时候已经修改的TrieTrieTrie树上的数组其实是可以直接往后走的。
之后我们就有了dpdpdp的方法valival_ivali表示在failfailfail树上iii节点到根节点的路径上有多少个串的结束位置。fi,jf_{i,j}fi,j表示现在填字符的iii个位置目前在TrieTrieTrie树上节点为jjj的最大答案。之后进行dpdpdp即可
时间复杂度O(3∗∑i1n∣si∣L)O(3*\sum_{i1}^n |s_i|L)O(3∗∑i1n∣si∣L) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N2100;
int n,L,cnt,ans;
int val[N],son[N][3],fail[N],f[N][N];
char s[N];
queueint q;
void Make(char *s){int x0,lenstrlen(s);for(int i0;ilen;i){int cs[i]-A;if(!son[x][c])son[x][c]cnt;xson[x][c];}val[x];return;
}
void Get_Fail(){for(int i0;i3;i)if(son[0][i])q.push(son[0][i]);while(!q.empty()){int xq.front();q.pop();for(int i0;i3;i)if(!son[x][i])son[x][i]son[fail[x]][i];else{q.push(son[x][i]);int yfail[x];fail[son[x][i]]son[y][i];}val[x]val[fail[x]];}return;
}
int main()
{scanf(%d%d,n,L);for(int i1;in;i){scanf(%s,s);Make(s);}Get_Fail();memset(f,0xcf,sizeof(f));f[0][0]0;for(int i1;iL;i)for(int j0;jcnt;j)for(int k0;k3;k){f[i][son[j][k]]max(f[i][son[j][k]],f[i-1][j]val[son[j][k]]);if(iL)ansmax(ans,f[i][son[j][k]]);}printf(%d,ans);
}
