CF 535D KMP

题意：给定一字符串s，和一个位置数组pos[]，在一个长为n的空字符串中，在每一个位置pos[i]处贴上s，当有重叠时，重叠的部分必须完全相同，问有多少种满足题意得字符串。
输入：
第一行两个整数：n m
第二行长为|s|的字符串
第三行为m个整数pos[i]
分析：在贴上m个s串之后，计算剩余的空位置cnt，输出答案26^cnt即可。那么难点转化为判断这m个s串是否能够完全相容。
既然要求每一个重叠的地方都要相同，如果重叠的部分长度为l，那其实就是说s需满足s的前l个字符和后l个字符相等。问题转化为s的前i个字符和后i个字符是否相等。我们知道kmp算法中的Next[]数组表示的是前i个字符中，前缀和后缀相同的最大长度，那如何表示出所有的前缀和后缀相同的长度呢。
Next[|s|]表示串s前缀和后缀相同的最大长度，即s[1,2,..Next[|s|]]=s[|s|-Next[|s|]+1,...,|s|],而在前Next[|s|]个字符中，也会有s[1,2,..Next[Next[|s|]]]=s[Next[|s|]-Next[Next[|s|]]+1,..,Next[|s|]],仔细想想这些头尾相等的字符串和子串的关系，就会发现，这是一个递归的过程。我们可以通过递归来求得|s|所有的前后缀相同的长度。
设mark[i]表示s的前i和后i个字符是否相同，在贴的时候只需判断重叠的部分是否被mark即可。

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5,mod = 1e9+7;
ll pow_mod(ll a,ll b);       //求a^b%mod
char p[maxn];
int pos[maxn],Next[maxn],mark[maxn];
int main(){
    int n,m,len;
    scanf ("%d %d %s",&n,&m,p+1);
    len = strlen(p+1);
    for(int i=2,j=0;i<=len;i++){         //Next数组求取
        while(j>0 && p[i]!=p[j+1]) j=Next[j];
        if(p[i]==p[j+1]) j++;
        Next[i]=j;
    }
    for (int i=len;i;i=Next[i]) mark[i] = 1;    //递归标记mark
    scanf ("%d",&pos[1]);
    for (int i=2;i<=m;i++){                    //检查是否可以构成母串
        scanf ("%d",&pos[i]);
        if (pos[i]-pos[i-1]>=len)   continue;
        if ( pos[i]+len-1>n || mark[len-(pos[i]-pos[i-1])]==0 ){
            printf("0");
            return 0;
        }
    }
    if(m)   n -= len;
    for (int i=2;i<=m;i++)                      //计算未被模式串覆盖的位置的个数
        n -= pos[i]-pos[i-1]<len?pos[i]-pos[i-1]:len;
    printf("%lld",pow_mod((ll)26,(ll)n));
    return 0;
}
ll pow_mod(ll a,ll b){
    a %= mod;
    if (a==0)   return 0;
    ll ans = 1;
    while (b){
        if (b&1)    ans = (ans*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return ans%mod;
}