题面
1 子串(substring.c/cpp/pas)
1.1 题目描述
给出一个长度为 n 的文本串，有 Q 次询问，每次给出一个字符串 s，询问 s 是否在文
本串中作为子串出现过。
1.2 输入格式
第一行为两个整数 n 和 Q，分别表示文本串长度和询问次数；
第二行为长为 n 的文本串；
接下来 Q 行，每行为一个字符串 s。
1.3 输出格式
输出 Q 行对应 Q 次询问的答案，若出现过则输出 YES，否则输出 NO。
1.4 样例输入
6 3
abdbec
e
bdb
aa
1.5 样例输出
YES
YES
NO
1.6 数据范围与约定
对于前 20％的数据 n、Q<=100；
对于前 40％的数据 n、Q<=5000；
对于 100％的数据 n、Q<=100000，且保证 s 为长度不超过 100000 的回文串且所有 s
的总长不超过 1000000，保证所有字符都是小写字母。
好的吧，其实这道题转成离线用AC自动机就是一道板子题了。
但是我们观察数据范围，发现给的
所有模式串都是回文串，那我们就可以考虑manacher的做法，把文本串中所有回文串存下，然后输入模式串的时候就看有没有这个回文串就可以了。
主要是想要说一下怎么用manacher去求本质不同的回文串。
我们知道一个很重要的性质,即：当回文串扩展时会出现本质不同的回文串。
那么在while扩展的时候存下的回文串就是本质不同的回文串。
#include<bits/stdc++.h>
#define N 100003
#define M 1000004
#define BASE 233
#define mod 1000005
#define LL unsigned long long
using namespace std;
char t[N],s[N*
2],a[N],b[M];
int len,ans=
0,num=
0,YES[N*
2];
int pal[N*
2];
map<
string,
int>
ma;
void init()
{
s[0]=
'-';
for(
int i=
1;i<
2*len;i+=
2)
{
s[i]=
'#';
s[i+
1]=t[i/
2];
}
s[2*len+
1]=
'#';
s[2*len+
2]=
'+';
s[2*len+
3]=
'\0';
len=
2*len+
1;
}
void manacher()
{
int id,mx=
0;
/* for(int i=1;i<=len;++i)
printf("%c",s[i]);
printf("\n");*/
for(
int i=
1;i<=len;i++
)
{
if(mx>=i) pal[i]=min(pal[
2*id-i],mx-i+
1);
else pal[i]=
1;
while(s[i-pal[i]]==s[i+
pal[i]])
{
pal[i]++;
//每次扩展时就会有新的回文串出现
int p=
0;
for(
int j=i-pal[i]+
2;j<i+pal[i]-
1;j+=
2)
a[p++]=
s[j];
a[p++]=
'\0';
ma[a]=
1;
}
if(i+pal[i]-
1>mx) mx=i+pal[i]-
1,id=
i;
ans+=pal[i]/
2;
}
}
int main()
{
// freopen("substring.in","r",stdin);
// freopen("substring.out","w",stdout);
int n,Q;
scanf("%d%d",&n,&
Q);
scanf("%s",t);
len=
n;
for(
int i=
0;i<len;++
i)
YES[t[i]-
'0']=
1;
init();
manacher();
for(
int i=
1;i<=Q;++
i)
{
scanf("%s",b);
int lenth=
strlen(b);
if(lenth>
n)
{
printf("NO\n");
continue;
}
else if(ma[b]) printf(
"YES\n");
else printf(
"NO\n");
}
}
View Code
emmm，说到这个就生气呢[○･｀Д´･ ○]，记得好像在哪里看到的求本质不同的回文串的板子，结果是错的，不仅求出的不是本质不同的，而且还会漏，rua。
然后还要提一嘴的是，以'\0'结尾的才能是字符串，不然在存入的时候会有问题。
转载于:https://www.cnblogs.com/yyys-/p/11191662.html
相关资源：数据结构—成绩单生成器
