求助,#2WA,几乎和 OI-Wiki 一模一样
查看原帖
求助,#2WA,几乎和 OI-Wiki 一模一样
366338
fjy666楼主2022/2/17 20:35

RT

#include <bits/stdc++.h>
#define _rep(i_,a_,b_) for(int i_ = a_;i_ <= b_;++i_)
typedef long long ll;
int in(void) { int x; scanf("%d",&x); return x; }
ll inl(void) { ll x; scanf("%lld",&x); return x; }
using namespace std;
const int kN = 1000005,kS = 26;
queue<int> Q;
namespace AC {
	int t[kN][kS],ncnt,val[kN],fail[kN];
	void insert(char *s) {
		int cur = 0;
		while(*s) {
			if(!t[cur][*s - 'a']) t[cur][*s - 'a'] = ++ncnt;
			cur = t[cur][*s - 'a']; ++s;
		}
		++val[cur];
	}
	void build(void) {
		for(int i = 0;i < 26;++i) if(t[0][i]) Q.push(i);
		while(!Q.empty()) {
			int u = Q.front(); Q.pop();
			for(int i = 0;i < 26;++i)
				if(t[u][i]) fail[t[u][i]] = t[fail[u]][i],Q.push(t[u][i]);
				else t[u][i] = t[fail[u]][i];
		}
	}
	int query(char *s) {
		int u = 0,ans = 0;
		while(*s) {
			u = t[u][*s - 'a'];
			int t = u;
			while(t && val[t]) ans += val[t],val[t] = 0,t = fail[t];
			++s;
		}
		return ans;
	}
}
char s[kN];
int main() {
	int n = in();
	_rep(i,1,n) {
		scanf("%s",s + 1);
		AC::insert(s + 1);
	}
	AC::build();
	scanf("%s",s + 1);
	printf("%d\n",AC::query(s + 1));
	return 0;
}
2022/2/17 20:35
加载中...