ios::sync_with_stdio(false);
cin.tie(0);
- \(\Uparrow\) 关闭同步/解除绑定，可以优化读入字符串的效率
- 这行代码的缺失，不仅导致程序在本地运行时需要过好几秒才能读入数据，更导致程序在OJ上评测时TLE
- 时隔半年，自己还能独自完成KMP和AC自动机的代码，还是比较开心的；调试时，把握整体，注意模块的错位
- 要对字典树的每个节点开一个动态数组，以处理字符串相同的情况
点击查看代码
#include <bits/stdc++.h>
using namespace std;
string a,c;
int t[100005][26],nx[100005],fail[100005];
bool ans[100005];
vector<int>id[100005];
string b1,b2;
void kmp()
{
nx[1]=0;
for(int i=2;i<=c.size();i++)
{
int j=nx[i-1];
while(j!=0&&c[j]!=c[i-1])
{
j=nx[j];
}
nx[i]=j;
if(c[j]==c[i-1])
{
nx[i]++;
}
}
nx[c.size()+1]=0;
}
bool pd(char *s,int n)
{
for(int i=c.size()+2;i<=n+c.size()+1;i++)
{
int j=nx[i-1];
while(j!=0&&c[j]!=s[i-1-(c.size()+1)])
{
j=nx[j];
}
nx[i]=j;
if(c[j]==s[i-1-(c.size()+1)])
{
nx[i]++;
}
if(nx[i]==c.size())
{
return true;
}
}
return false;
}
int tot;
int q[100005],l,r;
void insert(string s,int tag)
{
int p=0;
for(int i=0;i<s.size();i++)
{
if(t[p][s[i]-'a']==0)
{
tot++;
t[p][s[i]-'a']=tot;
id[tot].clear();
}
p=t[p][s[i]-'a'];
}
id[p].push_back(tag);
}
void pre()
{
l=1,r=0;
for(int i=0;i<26;i++)
{
if(t[0][i]>0)
{
r++;
q[r]=t[0][i];
}
}
while(l<=r)
{
int n1=q[l];
l++;
for(int i=0;i<26;i++)
{
if(t[n1][i]==0)
{
t[n1][i]=t[fail[n1]][i];
}
else
{
fail[t[n1][i]]=t[fail[n1]][i];
r++;
q[r]=t[n1][i];
}
}
}
}
void solve()
{
int p=0;
for(int i=0;i<a.size();i++)
{
p=t[p][a[i]-'a'];
int q=p;
while(q!=0)
{
for(int j=0;j<id[q].size();j++)
{
ans[id[q][j]]=true;
}
q=fail[q];
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
cin>>a>>c;
tot=0;
memset(fail,0,sizeof(fail));
memset(t,0,sizeof(t));
memset(id,0,sizeof(id));
kmp();
for(int i=1;i<=n;i++)
{
ans[i]=false;
cin>>b1>>b2;
if(pd(&b2[0],b2.size()))
{
insert(b1,i);
}
}
pre();
solve();
int cnt=0;
for(int i=1;i<=n;i++)
{
if(ans[i]==true)
{
cnt++;
if(cnt!=1)
{
cout<<" ";
}
cout<<i;
}
}
cout<<endl;
}
return 0;
}