AC 自动机求助 玄关
查看原帖
AC 自动机求助 玄关
464004
ZepX_D楼主2024/8/10 11:36

WA on 6,what can I say?

#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>

using namespace std;

inline int read()
{
	int x = 0;char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
	return x;
}

const int N = 2e5+5;
int tr[N][26],fa[N],cnt,ed[N];
LL f[N];
string s[N];

void ins(string s)
{
	int p = 0;
	for (char c : s)
	{
		int x = c-'a';
		if(!tr[p][x]) tr[p][x] = ++cnt;
		p = tr[p][x];
	}
	ed[p]++;
}

void build()
{
	queue < int > q;
	for (int i = 0;i < 26;i++)
		if(tr[0][i]) q.push(tr[0][i]);
	while(q.size())
	{
		int x = q.front();q.pop();
		ed[x] += ed[fa[x]];
		for (int i = 0;i < 26;i++)
		{
			if(tr[x][i]) fa[tr[x][i]] = tr[fa[x]][i],q.push(tr[x][i]);
			else tr[x][i] = tr[fa[x]][i];
		}
	}
}

int main()
{
	string t;cin >> t;
	int n = read();
	for (int i = 1;i <= n;i++)
		cin >> s[i],ins(s[i]);
	build();
	int p = 0;
	for (int i = 0;i < t.size();i++)
		p = tr[p][t[i]-'a'],f[i+1] = ed[p];
	LL ans = 0;p = 0;
	for (int i = t.size()-1;i >= 0;i--)
		p = tr[p][t[i]-'a'],ans += 1LL*f[i]*ed[p];
	cout << ans;
	return 0;
}
2024/8/10 11:36
加载中...