ZeroJudge-b179 空罐 Cans 可爱的AC自动机DP..

ZeroJudge-b179 空罐 Cans 可爱的AC自动机DP..

​​'b' 'c' 'd'利用Trie图进行转移这种很基本的操作..还有一个就是去掉自身的第一个字符..而本题的关键就是这个..而这个操作可以分为3种情况:

1.当前的长度为1..那么分裂完后显然就要丢资源回收站了..

2.当前长度大于当前p所在Trie树中的深度,那么其去掉首字母后还会停留在Trie树中的p点..

3.当前长度小于当前p所在Trie树中的深度,那么其去掉首字母后就需要转移了..沿着AC自动机的Fail指针去更新point[p].fail既是...

Program:

#include#include#include#include#include#define oo 2000000000#define ll long longusing namespace std; struct node1{ int son[4],fail,len; bool w;}point[1510];char s[105],str[105];int p,n,dp[2][103][1510];queue myqueue;int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int len,i,j,h,k,t,num,ans1,ans2; memset(point,0,sizeof(point)); scanf("%s%d%d",str,&p,&n); num=0; while (n--) { scanf("%s",s); len=strlen(s); h=0; for (i=0;ij-1) { t=point[i].fail; dp[k][j-1][t]+=dp[1-k][j][i]; dp[k][j-1][t]%=10007; }else { dp[k][j-1][i]+=dp[1-k][j][i]; dp[k][j-1][i]%=10007; } for (h=0;h<4;h++) { dp[k][j+1][point[i].son[h]]+=dp[1-k][j][i]; dp[k][j+1][point[i].son[h]]%=10007; if (point[point[i].son[h]].w) ans2=(ans2+dp[1-k][j][i])%10007; } } } printf("%d %d\n",ans1,ans2); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。