题面
题目描述
给你两个字符串a和b，告诉所有你b在a中一定匹配的位置，求有中不同的字符串a。a的长度为n，b的长度为m，一定匹配的位置有p个。若b在a中的一定匹配的位置为x，说明a[x…x+m-1]=b[1…m]。a和b中只有小写字母。
输入格式
第一行两个字符串n、p；（1<=n<=100000, 0<=p<=n-m+1）
第二行有一个字符串b；(1<=m<=n) 第三行有p个数：这p个一定匹配的位置。输出格式
一个数：答案。模10^9+7。
样例
Input1
6 2ioi1 3
Output1
26
Input2
5 2ioi1 2
Output1
0
样例解释
第一个样例中a的前5个字符为”ioioi”，最后一个字符可以是任意的字符，所以答案为26.
第二个样例中a的第二个字符不可能既是i又是o。题解
相邻出现的串假如没有重叠的化, 则空位直接统计;
假如出现重叠, 则用扩展KMP的\(match\)数组判断是否合法即可.#include#include #include const int L = 1000000, MOD = (int)1e9 + 7; int power(int a, int x){ int res = 1; for(; x; x >>= 1, a = (long long)a * a %MOD) if(x & 1) res = (long long)res * a % MOD; return res;} int main(){ #ifndef ONLINE_JUDGE freopen("Tavas.in", "r", stdin); #endif int n, P; scanf("%d%d\n", &n, &P); if(! P) { printf("%d\n", power(26, n)); return 0; } static char str[L]; scanf("%s", str); static int mch[L]; int len = strlen(str); mch[0] = len - 1; int p = 1; mch[p] = -1; for(; mch[p] + p < len && str[p + mch[p] + 1] == str[mch[p] + 1]; ++ mch[p]); int mx = mch[p]; for(int i = 2; i < len; ++ i) { mch[i] = std::max(0, std::min(mx - i, mch[i - p])); for(; i + mch[i] < len && str[i + mch[i] + 1] == str[mch[i] + 1]; ++ mch[i]); if(i + mch[i] > mx) p = i, mx = i + mch[i]; } static int pos[L]; for(int i = 0; i < P; ++ i) scanf("%d", pos + i); std::sort(pos, pos + P); int ans = power(26, pos[0] - 1); for(int i = 1; i < P; ++ i) { if(pos[i] - pos[i - 1] >= len) ans = (long long) ans * power(26, pos[i] - pos[i - 1] - len) % MOD; else if(pos[i] - pos[i - 1] < len) if(mch[pos[i] - pos[i - 1]] ^ len - (pos[i] - pos[i - 1]) - 1) ans *= 0; } if(n - pos[P - 1] < len) ans *= 0; printf("%d\n", (long long)ans * power(26, n - pos[P - 1] - len + 1) % MOD);}