又复习了一遍kmp....之前都忘光了
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 1e6+5; 20 int next[maxn], a[maxn], vis[maxn], used[maxn]; 21 char s[maxn]; 22 void get_next() { 23 int len = strlen(s); 24 int i = 0, j = -1; 25 next[0] = -1; 26 while(i<len) { 27 if(j==-1 || s[i] == s[j]) { 28 i++, j++; 29 next[i] = j; 30 } else { 31 j = next[j]; 32 } 33 } 34 int pos = next[len]; 35 while(pos != -1) { 36 vis[pos] = 1; 37 pos = next[pos]; 38 } 39 return ; 40 } 41 int main() 42 { 43 int n, m; 44 cin>>n>>m; 45 scanf("%s", s); 46 int len = strlen(s); 47 get_next(); 48 for(int i = 1; i<=m; i++) { 49 scanf("%d", &a[i]); 50 } 51 sort(a+1, a+m+1); 52 int flag = 0; 53 for(int i = 1; i<=m; i++) { 54 if(i == 1 || a[i]-a[i-1]>len) { 55 for(int j = a[i]; j<len+a[i]; j++) { 56 used[j] = 1; 57 } 58 } else { 59 if(vis[len+a[i-1]-a[i]]) { 60 for(int j = a[i-1]+len; j<len+a[i]; j++) { 61 used[j] = 1; 62 } 63 } else { 64 flag = 1; 65 break; 66 } 67 } 68 } 69 if(flag) { 70 puts("0"); 71 return 0; 72 } 73 ll ans = 1; 74 for(int i = 1; i<=n; i++) { 75 if(!used[i]) { 76 ans = (ans*26)%mod; 77 } 78 } 79 cout<<ans<<endl; 80 return 0; 81 }