2019暑假集训DAY6（problem1.substring）（manacher+map）

题面

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

bdb

1.5 样例输出

YES

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]='';
    len=2*len+1;
}
void manacher()
{
    int id,mx=0;
/*    for(int i=1;i<=len;++i)
    printf("%c",s[i]);
    printf("
");*/
    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++]='';
            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
");continue;
        }
        else if(ma[b]) printf("YES
");
        else printf("NO
");
    }
}

View Code

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

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