CF 299 div2 D. Tavas and Malekas(KMP)

题目：http://codeforces.com/contest/535/problem/D

题意：给定文本串T的长度为L和模式串P在文本串T的首位置的个数n,再给出模式串P,然后给出n个数,代表模式串P在文本串T的首位置。求文本的可能情况,结果模上109 + 7。

分析：这题主要是判断模式串P填在文本串T里面是否合法,如果不合法,那么答案就是0,如果合法就看文本串T里面有多少个位置没有填,记为x,那么结果就是26^x。直接往文本串里面填模式串的话会超时。判断是否合法，其实就是往文本串T里面填模式串P判断两个模式串的重叠部分是否匹配,即判断模式串的前缀和后缀是否匹配,这就要用到KMP算法。首先求出next数组(next数组不能优化),利用next数组将可重叠的长度全部存进查询表,往文本串T里面填模式串P的时候求出模式串的重叠长度,然后再查询表里面找长度是否存在,若不存在就不合法,若存在就继续....

代码：

/*
ID: 15507481
PROG: test
LANG: C++11
*/
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <queue>
#include <stack>
#include <deque>

using namespace std;
typedef long long LL;
#define MAXN 2000000
#define MOD 1000000007ll
char sub[MAXN];
int pos[MAXN];
int Next[MAXN];
bool match[MAXN];

void getnext(int Next[],char str[]);

LL my_pow(int n)
{
	LL ret=1ll,a=26ll;
	while(n)
	{
		if(n&1)
			ret=ret*a%MOD;
		n>>=1;
		a=a*a%MOD;
	}
	return ret%MOD;
}

int main()
{
	int N,num,i,j,k;
	scanf("%d%d",&N,&num);
	scanf("%s",sub);
	int len=strlen(sub);
	sub[len]='&';
	sub[len+1]='\0';
	len++;
	for(i=0;i<num;i++)
		scanf("%d",&pos[i]);
	getnext(Next,sub);
	int pos1=len-1;
	while(Next[pos1]!=-1)
	{
		match[Next[pos1]]=true;
		pos1=Next[pos1];
	}
	int ans=0;
	bool tag=true;
	for(i=1;i<num;i++)
	{
		if(pos[i-1]+len-2<pos[i])
		{
			ans+=pos[i]-(pos[i-1]+len-2)-1;
		}
		else
		{
			if(!match[pos[i-1]+len-2-pos[i]+1])
			{
				tag=false;
				break;
			}
		}
	}
	if(num==0)
		ans=N;
	else
	{
		ans+=N-(pos[num-1]+len-2);
		ans+=pos[0]-1;
	}
	if(tag)
		cout<<my_pow(ans)<<'\n';
	else
		printf("0\n");
    return 0;
}


void getnext(int Next[],char str[])
{
	int len=strlen(str);
	Next[0]=-1;
	int k=-1;
	int j=0;
	while(j<len)
	{
		if(k==-1 ||str[j]==str[k])
		{
			j++;
			++k;
			Next[j]=k;
		}
		else
			k=Next[k];
	}
}

/*
 *
 *
 *
 *
 *
 *
*/