求助...
查看原帖
求助...
338492
Michael·F·Chen楼主2022/9/26 18:08

测了很多组数据,把udebug上的数据也测了,对着题解也测了,结果还是WA,不知道哪里出问题了...每次都是卡在最后WA的,不知道忽略的什么情况,但是感觉每一步几乎都题解一样...

#include <bits/stdc++.h>
using namespace std;

const int N=300005;
const int P=20071027;

int n,cnt,f[N];
char s[N];
struct Node{
	int son[26];
	bool yon;
}node[N],emp;

char ss[105];
inline void Insert(){
	scanf("%s",ss+1);
	int len=strlen(ss+1);
	int x=0;
	for(int i=1;i<=len;++i){
		if(!node[x].son[ss[i]-'a'])
			node[x].son[ss[i]-'a']=++cnt;
		x=node[x].son[ss[i]-'a'];
	} node[x].yon=true;
}

int main(){
//  freopen("words.in","r",stdin);
//  freopen("words.out","w",stdout);
  int t=0;
  while(~scanf("%s",s+1)){
  	cnt=0;
		memset(f,0,sizeof(f));
		for(int i=0;i<=N;++i) node[i]=emp;
		
		scanf("%d",&n);
  	while(n--) Insert();
  	
  	int len=strlen(s+1); f[len+1]=1;
		for(int i=len;i>0;--i){
			int x=0,l=0;
			while(node[x].son[s[i+l]-'a']&&i+l<=len){
				x=node[x].son[s[i+l]-'a'];
				++l;
				if(node[x].yon) f[i]=(f[i]+f[i+l])%P;
			}
		}
		
		printf("Case %d: %d\n",++t,f[1]);
	}
  return 0;
}
2022/9/26 18:08
加载中...