题目链接
题意：给定字符串s的长度n, x1,x2,…xk中选取m个位置
给定字符串p
y1,y2,…,ym
x1,x2,…xk中每个xi满足sxisxi+1…sxi+|p|-1=p
求满足条件的字符串有多少种，对10^9+7取模
思路：首先对字符串p构造fail函数，fail[ i ]表示当前位失配时转移到的位置，深究下其性质，就是i位置所能匹配的最长字符串的长度为fail[ i+1 ]。那么考虑yi-1,yi，，如果两段字符串有相交，需判断相交部分是否是匹配，判断时利用fail函数性质，即不断沿fail函数向前走，如果有函数值等于相交段的长度就说明相交部分可以匹配。如果每对yi-1,yi都可以匹配，那么只需要扫一下字符串看哪些位置可以填任何字母，用num记录这种位置的数量，最后的答案就是26^num对10^9+7取模。详见代码：
/********************************************************* file name: codeforces535D.cpp author : kereo create time: 2015年04月19日 星期日 23时16分03秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;typedef unsigned long long ull;const int sigma_size=26;const int N=100+50;const int MAXN=1000000+50;const int inf=0x3fffffff;const double eps=1e-8;const int HASH=100007;const int mod=1000000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define Ls(x) (x->ch[0])#define Rs(x) (x->ch[1])#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int n,m,len;char str[MAXN];int fail[MAXN];void get_fail(){int i=0,j=-1;fail[0]=-1;while(i<len){if(j == -1 || str[i] == str[j]){i++; j++; fail[i]=j;}elsej=fail[j];}}ll num_pow(ll a,ll k){ll ans=1;while(k){if(k&1)ans=(ans*a)%mod;a=(a*a)%mod;k>>=1;}return ans;}int main(){//freopen("in.txt","r",stdin);while(~scanf("%d%d",&n,&m)){scanf("%s",str);len=strlen(str); get_fail();int last=-1,ok=1,num=0,pre;for(int i=0;i<m;i++){int now;scanf("%d",&now);now–;num+=max(0,now-last-1);int l=pre+len-now; pre=now;if(i == 0){last=now+len-1;continue;}last=now+len-1;if(l<0)continue;int cur=len;while(fail[cur]!=-1){if(fail[cur] == l)break;cur=fail[cur];}if(fail[cur] == -1){ok=0;}}num+=n-last-1;if(!ok){printf("0\n");continue;}elseprintf("%lld\n",num_pow(26,num));}return 0;}
阳光总在风雨后。只有坚强的忍耐顽强的奋斗，
