本文主要是介绍codeforces535D Tavas and Malekas kmp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题意：给定字符串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.cppauthor : kereocreate 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;}else j=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;
}
这篇关于codeforces535D Tavas and Malekas kmp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
