535D Tavas and Malekas

题目大意

给你一个串和m个下标

问你一个长度为n的串每一个下标开始的后缀的前缀都包含给定的串的方案数

分析

对于给定的串求出z数组

对于两个串不重叠的情况就是中间都不包含的数随便填即可

对于重叠的情况判断相交部分的左端点的z[i]是否大于等于重叠长度即可

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int mod = 1e9+;

int n,m,q,z[],ans,wh[],pw[];

char s[];

inline void get_z(){

    int i,j,k,l=,r=;

    z[]=n;

    for(i=;i<n;i++){

      if(i<=r)z[i]=min(r-i+,z[i-l]);

      while(i+z[i]<n&&s[z[i]]==s[z[i]+i])z[i]++;

      if(i+z[i]->r)r=i+z[i]-,l=i;

    }

}

int main(){

    int i,j,k;

    scanf("%d%d",&m,&q);

    scanf("%s",s);

    n=strlen(s);

    get_z();

    pw[]=;

    for(i=;i<=;i++)pw[i]=1ll*pw[i-]*%mod;

    for(i=;i<=q;i++)scanf("%d",&wh[i]);

    if(!q){

      printf("%d\n",pw[m]);

      return ;

    }

    ans=pw[wh[]-];

    int la=wh[]+n-;

    for(i=;i<=q;i++){

      if(wh[i]>la)ans=1ll*ans*pw[wh[i]-la-]%mod;

        else {

          if(z[n-la+wh[i]-]<la-wh[i]+){

              puts("");

              return ;

          }

        }

      la=wh[i]+n-;

      if(la>m){

          puts("");

          return ;

      }

    }

    if(m>la)ans=1ll*ans*pw[m-la]%mod;

    printf("%d\n",ans);

    return ;

}