【Codeforces Round #299 (Div. 2) D】Tavas and Malekas

给你n个位置,然后让你从某些位置开始的|p|个位置,填上p这个字符串. 问你填的时候是否会发生冲突->输出0 否则输出最终n个位置组成的可能的字符串的总数

【题解】

扩展KMP. 画个图会发现。相邻的两个填写操作。只要发生了重叠。想要看有没有冲突。相当于询问从某个位置开始的后缀是否和从0开始的后缀一样。即看看lcp的长度是否大于等于相交部分即可。会发现第i-2个字符串如果没有和第i-1个字符串发生冲突。那么和第i个字符串如果发生了重叠,那么肯定也不会发生冲突.->画图就知道了注意不插入的情况。

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N=1e6;
int Next[N+10],extend[N+10],lent,lens;
char S[N+10],T[N+10];

void makenext(int m){
    int a = 0;
    Next[0] = lens;
    while(a < lens - 1 && S[a] == S[a + 1]) a++;
    Next[1] = a;
    a = 1;
    for(int k = 2; k < lens; k ++) {
        int p = a + Next[a] - 1,L = Next[k - a];
        if( (k - 1) + L >= p) {
            int j = (p - k + 1) > 0 ? (p - k + 1) : 0;
            while(k + j < lens && S[k + j] == S[j]) j++;
            Next[k] = j;
            a = k;
        } else
            Next[k] = L;
    }
}

void GetNext(const char *T){
     int a=0;
     int MinLen = lens < lent ? lens : lent;
     while(a < MinLen && S[a] == T[a] ) a++;
     extend[0]=a;
     a=0;
     for(int k=1;k < lent;k++){
         int p=a+extend[a]-1,L = Next[k-a];
         if((k-1)+L>=p){
             int j=(p-k+1)>0? (p-k+1):0;
             while(k + j < lent && T[k+j] == S[j]) j++;
             extend[k]=j;
             a=k;
         }
         else extend[k]=L;
     }
}

int flag[N+10];

int main(){
	int ma,m;
	scanf("%d%d",&ma,&m);
	scanf("%s",S);
	strcpy(T,S);
    lent = strlen(T),lens = strlen(S);
    makenext(lens);
    GetNext(T);

	int x1 = -1e9;
    while (m--){
		int x;
		scanf("%d",&x);
		if (x1+lens-1<x){
			for (int i = max(1,x1+lens);i <= x-1;i++){
			 	flag[i] = 1;
			}
		}else{
			int overlap = x1+lens-1-x+1;
			int p = lens-1-overlap+1;
			int temp = extend[p];
			if (temp<overlap){
			 	puts("0");
			 	return 0;
		 	}
		}
		x1 = x;
    }

    for (int i = max(1,x1+lens);i <= ma;i++) flag[i] = 1;

    long long ans =1;
    for (int i = 1;i <= ma;i++)
    	if (flag[i]==1){
    	    ans = (ans*26)%((int)(1e9+7));
    	}	

    printf("%lld
",ans);
	return 0;
}