题面

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
       
        #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
        
         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
         
          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
          
           n)        {            printf("NO\n");continue;        }        else if(ma[b]) printf("YES\n");        else printf("NO\n");    }}
          
         
        
       

emmm，说到这个就生气呢[○･｀Д´･ ○]，记得好像在哪里看到的求本质不同的回文串的板子，结果是错的，不仅求出的不是本质不同的，而且还会漏，rua。

然后还要提一嘴的是，以'\0'结尾的才能是字符串，不然在存入的时候会有问题。