求助大佬,本地编译没错,但WA了
查看原帖
求助大佬,本地编译没错,但WA了
352072
白百妖楼主2024/4/10 19:31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;

inline ll read(){
	char _c=getchar();ll _x=0, _f=1;
	for(;!isdigit(_c);_c=getchar()) if(_c=='-') _f=-1;
	for(;isdigit(_c);_c=getchar()) _x=_x*10+_c-'0';
	return _x*_f;
}

ll all_len=1, len, ans, s_ans;
ll tire[N][30], fail[N];
char c;
char son[N], s[N];

void set_tire(char c[], ll len){
	ll x=1;
	
	for(int i=1;i<=len;i++){
		if( !tire[x][ c[i]-'a' ] ) tire[x][ c[i]-'a' ]= ++all_len;
		x=tire[x][ c[i]-'a' ];
	}
	
	fail[x]=len;
}

void do_find(){
	ll x=1;
	
	for(int i=1;i<=len;i++){
		if( tire[x][ s[i]-'a' ] ) ; 
		else{//此枝无法匹配 
			
			if( !tire[1][s[i]-'a'] ){//重新从根开始找,若根没有建边直接退出循环 
			    ans+=s_ans;
				break;
			}
			else{//若建边 则进行对边的寻找 
				ans+=s_ans;
				x=1;
			}
			
		}
		x=tire[x][ s[i]-'a' ];
		
		if( fail[x] ) s_ans=fail[x];//计算前缀和 
		else s_ans=0;
	}
	
}

int main(){
	while( scanf("%c",&c)==1 ){
		
		if(c>='A' && c<='Z') son[ ++len ]=c;
		else{
			if(c=='\n') continue ;//跳过换行符 
			set_tire(son, len);
			len=0;
			
			if(c=='.') break;//结束标志 
		}
			
    }
	
	len=0;
	while( scanf("%c",&c)==1 ) if(c!='\n')  s[ ++len ]=c;
	
	do_find();
	printf("%lld\n%lld", ans, all_len);
	return 0;
}
2024/4/10 19:31
加载中...