萌新妹子刚学OI10^-114秒,70tps求助!
查看原帖
萌新妹子刚学OI10^-114秒,70tps求助!
795344
lfxxx_楼主2024/8/13 16:01
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=1e5+5;
int n,m;
int tr[M][26],exist[M],fail[M],tot;
void insert(string s,int x)
{
	int p=0;
	for(int i=0;i<(int)s.size();++i)
	{
		int k=s[i]-97;
		if(!tr[p][k])
			tr[p][k]=++tot;
		p=tr[p][k];
	}
	exist[p]=x;
}
void build()
{
	queue<int>q;
	for(int i=0;i<26;++i)
		if(!tr[0][i])
			q.emplace(tr[0][i]);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=0;i<26;++i)
			if(tr[u][i])
				fail[tr[u][i]]=tr[fail[u]][i],q.emplace(tr[u][i]);
			else
				tr[u][i]=tr[fail[u]][i];
	}
}
int query(string s)
{
	int p=0,res=0;
	for(int i=0;i<(int)s.size();++i)
	{
		p=tr[p][s[i]-97];
		for(int u=p;u&&~exist[u];u=fail[u])
			exist[u]=-1,res+=exist[u];
	}
	return res;
}
signed main()
{
	int a,b;cin>>a>>b;
	insert("IAKIOI",a);
	insert("TYWLOVELHQ",b);
	cout<<query("IAKIOITYWLOVELHQ");
}


2024/8/13 16:01
加载中...