【題解】Codeforces 536B. Tavas and Malekas

【題目敘述】http://codeforces.com/contest/536/problem/B

#include <bits/stdc++.h>
using namespace std;
 
int n, m, z[1000005], a[1000005];
long long ans = 1, mod = 1e9+7;
string s;
set <int> st;
 
int main(){
    cin >> n >> m;
    cin >> s;
    z[0] = s.size();
    int l = 0, r = 0;
    for (int i = 1; i < s.size(); i++){
        if (i <= r){
            if (z[i-l] >= r-i+1){
                l = i;
                r++;
                while (r < s.size() && s[r] == s[r-l]) r++;
                r--;
                z[i] = r-l+1;
            }
            else z[i] = z[i-l];
        }
        else{
            l = i;
            r = l;
            while (r < s.size() && s[r] == s[r-l]) r++;
            r--;
            z[i] = r-l+1;
        }
        //cout << l << " " << r << " " << z[i] << "\n";
    }
    if (m){
        cin >> a[0];
        st.insert(a[0]);
    }
    for (int i = 1; i < m; i++){
        cin >> a[i];
        st.insert(a[i]);
        int gap = (int)s.size()-(a[i]-a[i-1]);
        if (gap <= 0) continue;
        if (z[(int)s.size()-gap] != gap){
            cout << 0 << "\n";
            return 0;
        }
    }
    st.insert(-1e9);
    for (int i = 1; i <= n; i++){
        if (*prev(st.upper_bound(i))+(int)s.size() <= i){
            ans *= 26;
            ans %= mod;
        }
    }
    cout << ans << "\n";
}
分享本文 Share with friends