D. Tavas and Malekas
time limit per test
memory limit per test
input
output
Tavas is a strange creature. Usually "zzz" comes out of people's mouth while sleeping, but string s of length n
s. Malekas has a favorite string p. He determined all positions x1 < x2 < ... < xk where p matches s. More formally, for each xi (1 ≤ i ≤ k) he condition sxisxi... sxi + |p| - 1 = pis fullfilled.
x1, x2, ... xk (possibly, he didn't write anything) on a piece of paper. Here a sequence b is a subsequence of sequence a if and only if we can turn a into b
s, but he knew that both p and s
s? He asked SaDDas, but he wasn't smart enough to solve this. So, Tavas asked you to calculate this number for him.
109.
Input
n and m, the length of s and the length of the subsequence Malekas wrote down (1 ≤ n ≤ 106 and0 ≤ m ≤ n - |p| + 1).
p (1 ≤ |p| ≤ n).
m space separated integers y1, y2, ..., ym, Malekas' subsequence (1 ≤ y1 < y2 < ... < ym ≤ n - |p| + 1).
Output
1000 000 007.
Examples
input
6 2 ioi 1 3
output
26
input
5 2 ioi 1 2
output
0
在字符串s中， s[v1..v1+p-1]是p字符串, s[v2..v2+p-1]也是p字符串，v2 可能会小于等于v1+p-1，那么现在就是要判断s[v2..v1+p-1]是s的前缀也是后缀，用KMP判断即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define maxn 1000005
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n, m, num[maxn];
char str[maxn];
int vis[maxn], next[maxn];
void KMP(){
int i = 0, k = -1;
next[0] = -1;
while(str[i]){
if(k == -1 || str[i] == str[k]){
i++;
k++;
next[i] = k;
}
else
k = next[k];
}
}
int main(){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
scanf("%s", str);
for(int i = 0; i < m; i++)
scanf("%d", num+i);
KMP();
int len = strlen(str);
int pos = len;
while(pos){
vis[next[pos]] = 1;
pos = next[pos];
}
int pre = -1, ans = 0;
for(int i = 0; i < m; i++){
if(num[i] > pre){
ans += len;
pre = num[i] + len - 1;
}
else{
int d = pre - num[i] + 1;
if(vis[d] == 0){
puts("0");
return 0;
}
ans += len - d;
pre = num[i] + len - 1;
}
}
n -= ans;
ll p = 1;
while(n--){
(p *= 26) %= MOD;
}
printf("%I64d\n", p);
return 0;
}