题意：
给你一个字串，告诉你它在原串中出现的位置
让你求原串的种类数。
解题思路：KMP 性质的应用，有点类似于 http://www.cnblogs.com/zyue/p/4423049.html 这题。
解题代码：
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2015年04月15日 星期三 14时45分20秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define M 1000000007 26 using namespace std; 27 char str[1000005]; 28 int a[1000005]; 29 int next[1000005]; 30 int hs[1000005]; 31 int len ; 32 void get_next() 33 { 34 int k = -1; 35 next[0] = -1; 36 int j = 0 ; 37 while(j < len){ 38 if(k == -1 || str[j] == str[k]){ 39 ++ k ; 40 ++ j ; 41 next[j] = k ; 42 }else{ 43 k = next[k]; 44 } 45 } 46 } 47 void dfs(int k){ 48 if(k == 0 ) 49 return ; 50 hs[len - k + 1] = 1; 51 dfs(next[k]); 52 } 53 LL Pow(int k) 54 { 55 if(k < 0) 56 return 0; 57 LL ans = 1; 58 for(int i = 1;i <= k; i ++) 59 ans = ans * 26 % M; 60 return ans; 61 } 62 int main(){ 63 int n , m ; 64 scanf("%d %d",&n,&m); 65 scanf("%s",str); 66 len = strlen(str); 67 get_next(); 68 dfs(next[len]); 69 LL ans = 1 ; 70 if(m != 0 ) 71 { 72 scanf("%d",&a[1]); 73 ans = Pow(a[1]-1); 74 } 75 for(int i= 2;i<= m;i++){ 76 scanf("%d",&a[i]); 77 if(a[i] - a[i-1] < len) 78 { 79 if(hs[a[i]-a[i-1]+1] == 0 ) 80 { 81 printf("0 "); 82 return 0 ; 83 } 84 }else{ 85 ans = ans * Pow(a[i]-a[i-1]-len)%M; 86 } 87 } 88 //printf("%d %I64d ",n-a[m]-len+1,ans); 89 if(m != 0 ) 90 ans = ans * Pow(n-a[m]-len + 1) % M; 91 else 92 ans = Pow(n); 93 // for(int i= 1;i <= len ;i ++) 94 // printf("%d ",hs[i]); 95 printf("%I64d ",ans); 96 return 0; 97 }