本文主要是介绍codeforces535D:Tavas and Malekas(KMP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
(i-1 , i)有重合的时候 ,从第i位开始的子串必须是模式串的前缀。
而同时，从第i位开始的子串本来就已经是模式串的后缀了。
typedef long long LL ;const int maxn = 1000008 ;
int next[maxn] ;void getnext(char s[]){int len = strlen(s) ;next[0] = -1 ;int i = 0 , j = -1 ;while(i < len){if(j == -1 || s[i] == s[j]) next[++i] = ++j ;else j = next[j] ;}
}char word[maxn] ;
int x[maxn] ;const LL mod = 1000000007LL ;LL Pow(LL x , int y){LL s = 1 ;for(; y ; y >>= 1){if(y & 1){s *= x ; s %= mod ;}x *= x ; x %= mod ;}return s ;
}int n , m , len ;
set<int> st ;LL ans(){if(m == 0) return Pow(26LL , n) ;LL sum = Pow(26LL , x[1] - 1) ;for(int i = 2 ; i <= m ; i++){if(x[i] - x[i-1] >= len){sum *= Pow(26LL , x[i] - x[i-1] - len) ;sum %= mod ;}else{if(st.find(x[i] - x[i-1] + 1) == st.end()) return 0 ;}}sum *= Pow(26LL , n - x[m] - len + 1) ;sum %= mod ;return sum ;
}int main(){while(cin>>n>>m){scanf("%s" , word) ;getnext(word) ;for(int i = 1 ; i <= m ; i++) scanf("%d" , &x[i]) ;len = strlen(word) ;st.clear() ;int i = len ;while(next[i] != 0){st.insert(len - next[i] + 1) ;i = next[i] ;}cout<< ans() << endl ;}return 0 ;
}
这篇关于codeforces535D:Tavas and Malekas(KMP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
