大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=4147
#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define ll long long const int N =4000*100+100; const int MOD =20071027; char str[300019],pat[115]; ll dp[300019]; const int tk=26,tb='a'; int top,tree[N][tk+1],len; void init() { top=1; memset(tree[0],0,sizeof(tree[0])); } int sear(char*s,int i) { int cnt=0; ll ans=0; for(int rt=0;rt=tree[rt][*s-tb] ;++s) { if(*(s)==0)break; cnt++; if(tree[rt][tk])//cnt!=tree[rt][tk]表示dp[i..len-1]是一个单词,此时没有添加切割的种数 { if(*(s+1)==0)ans++; ans=(ans+dp[i+cnt])%MOD; ////////////////////// //printf("rt=%d s=%s i=%d cnt=%d dp=%lld\n",rt,str+i+cnt,i,cnt,dp[i]); ////////////////////// } } return ans; } void Insert(char*s, int Rank=0)//Rank为长度 { int rt,nxt; for(rt=0;*s;rt=nxt,++s,Rank++) { nxt=tree[rt][*s-tb]; if(0 == nxt)//nxt!=0的时候就是有公共前缀了。已经在之前做过了,仅仅需继续跳转即可he中插入her,到h,e都是nxt!=0不用插入 { tree[rt][*s-tb]=nxt=top; memset(tree[top],0,sizeof(tree[top])); top++; } } tree[rt][tk]=Rank; } int main() { //freopen("uva1401.txt","r",stdin); int n,ncase=1,pos; while(scanf("%s",str)!=EOF) { init(); pos=0; len=strlen(str); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",pat); Insert(pat); } dp[len]=0; for(int i=len-1;i>=0;i--) { dp[i]=0; dp[i]=sear(str+i,i); } printf("Case %d: %lld\n",ncase++,dp[0]); } return 0; }
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116891.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...