Tavas and Malekas

Created by LXC on Tue Jun 20 08:46:07 2023

https://codeforces.com/problemset/problem/535/D

ranting: 1900

tag: greedy, hashing, string suffix structures, strings

problem

有个一个长度为n的未知串s，和一个长度为p的已知串t。

给出m长度的非降序数组$a_1, a_2, \cdots, a_m$。

问满足$s[a_i,a_i+p-1] = t$的串有多少种？

字符串仅由小写英文字母组成。

solution

如果设字符串下标从0开始。

我们设覆盖的最右端的位置+1为r。

显然当前点$a_i$如果小于r，设$d=r-a_i$，当$s[0…d-1] \ne s[p-d…p-1]$，会产生覆盖的冲突，答案为0。
否则有$r-a_i$个自由字符，根据乘法原理答案累乘$26^{r-a_i}$。

现在关键在于判断字符串的前后缀是否相等。可以用很多种方法。

使用字符串哈希，这是个概率算法。有测试用例出现哈希冲突。使用多重哈希大大增加通过概率。

最后用后缀数组ac了。这个板子确实好用。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1000006
#define MOD 1000000007
#define ull unsigned long long
#define BASE 151
using namespace std;

// 单哈希容易被卡，封装用多重哈希
// 两个串的哈希相等，说明串大概率相等。
// struct Hash {
// #define ull unsigned long long
//     // string s[] index from 0 to n-1
//     // B[i] = BASE^i
//     // s[i...j] = s[0...j] - s[0...i-1]
//     // hash s[0...i-1] = H[i] = s[0]*B[i-1]+s[1]*B[i-2]+...+s[i-1]*B[0]
//     // hash s[0...j] = H[j+1] = s[0]*B[j]+s[1]*B[j-1]+...+s[j]*B[0]
//     // hash s[i...j] = H[j+1] - H[i]*B[j-i+1]
//     // hash s[i...j-1] = H[j] - H[i]*B[j-i]
//     vector<ull> H, B;
//     ull len, base, mod;
//     Hash(string& s, ull base = 131, ull mod = 998244353)
//         : H(s.size() + 1, 0),
//           B(s.size() + 1, 1),
//           len(s.size()),
//           base(base),
//           mod(mod) {
//         for (int i = 1; i <= len; i++) {
//             H[i] = (H[i - 1] * base % mod + s[i - 1]) % mod;
//             B[i] = B[i - 1] * base % mod;
//         }
//     }
//     ull hash(int l, int r) {  // hash of s[l...r-1]
//         return (H[r] - H[l] * B[r - l] % mod + mod) % mod;
//     };
// };

// struct Checker {
//     vector<Hash> h;
//     Checker(string& s) {
//         // MOD 太大会溢出, 应在sqrt(ull)内
//         vector<pair<ull, ull>> param = {{131ull, 998244353ull},
//                                         {151ull, 1000000007ull},
//                                         {171ull, 998244357ull}};
//         for (auto [i, j] : param) {
//             h.emplace_back(s, i, j);
//         }
//     }
//     // is s[l1...r1-1] == s[l2...r2-1] ? s[] index from 0
//     bool check(int l1, int r1, int l2, int r2) {
//         for (auto& i : h) {
//             if (i.hash(l1, r1) != i.hash(l2, r2))
//                 return false;
//         }
//         return true;
//     }
// };

// void sol() {
//     int n, m;
//     string s;
//     cin >> n >> m >> s;
//     int len = s.size();
//     Checker ck(s);
//     ll ans = 1, r = 0;
//     for (int i = 0; i < m; i++) {
//         int p;
//         cin >> p;
//         p--;
//         if (p < r) {
//             int d = r - p;
//             if (!ck.check(len - d, len, 0, d)) {
//                 cout << "0\n";
//                 return;
//             }
//         } else {
//             for (int i = r; i < p; i++)
//                 ans *= 26, ans %= MOD;
//         }
//         r = p + len;
//     }
//     for (; r < n; r++)
//         ans *= 26, ans %= MOD;
//     cout << ans << "\n";
// }

// 后缀数组，生成sa，rk，height数组
// range应大于串的长度和串元素最大值。串中元素值应非负。
template <class T = string, int range = 128>
struct SuffixArray {
    T s;
    int n, bucketRange;
    int sa[range], second[range], bucket[range], mem[range], rk_mem[range + 1],
        rk2_mem[range + 1], height[range], *rk, *rk2;
    SuffixArray(const T& _s) : s(_s), n(s.size()), bucketRange(range) {
        rk = rk_mem;
        rk2 = rk2_mem;
        rk[n] = rk2[n] = -1;
        memset(bucket, 0, sizeof(bucket));
        for (int i = 0; i < n; i++)
            bucket[rk[i] = s[i]]++;
        for (int i = 1; i < bucketRange; i++)
            bucket[i] += bucket[i - 1];
        for (int i = 0; i < n; i++)
            sa[--bucket[rk[i]]] = i;
        for (int w = 1;; w <<= 1) {
            int j = 0;
            for (int i = n - w; i < n; i++)
                second[j++] = i;
            for (int i = 0; i < n; i++)
                if (sa[i] >= w)
                    second[j++] = sa[i] - w;
            memset(bucket, 0, sizeof(bucket));
            for (int i = 0; i < n; i++)
                bucket[mem[i] = rk[second[i]]]++;
            for (int i = 1; i < bucketRange; i++)
                bucket[i] += bucket[i - 1];
            for (int i = n - 1; i >= 0; i--)
                sa[--bucket[mem[i]]] = second[i];
            bucketRange = 0;
            for (int i = 0; i < n; i++) {
                rk2[sa[i]] = !i || (rk[sa[i]] == rk[sa[i - 1]] &&
                                    rk[sa[i] + w] == rk[sa[i - 1] + w])
                                 ? bucketRange
                                 : ++bucketRange;
            }
            swap(rk, rk2);
            if (++bucketRange == n)
                break;
        }
    }
    void getHeight() {
        memset(height, 0xff, sizeof(height));
        for (int i = 0, h = 0; i < n; i++) {
            if (h)
                h--;
            if (rk[i])
                while (sa[rk[i] - 1] + h < n &&
                       s[i + h] == s[sa[rk[i] - 1] + h])
                    h++;
            height[rk[i]] = h;
        }
    }
};

void sol() {
    int n, m;
    string s = "aabaaaab";
    cin >> n >> m >> s;
    int len = s.size();
    auto SA = new SuffixArray<string, N>(s);
    SA->getHeight();
    auto& sa = SA->sa;
    auto& rank = SA->rk;
    auto& height = SA->height;
    vector<int> lcp(len, len);  // 后缀i与后缀0的公共前缀长度
    for (int i = rank[0], j = N; i >= 1; i--) {
        j = min(j, height[i]);
        lcp[sa[i - 1]] = j;
    }
    for (int i = rank[0] + 1, j = N; i < len; i++) {
        j = min(j, height[i]);
        lcp[sa[i]] = j;
    }
    // for (int i : lcp) {
    //     cout << i << " ";
    // }
    ll ans = 1, r = 0;
    for (int i = 0; i < m; i++) {
        int p;
        cin >> p;
        p--;
        if (p < r) {
            int d = r - p;
            if (lcp[len - d] != d) {
                cout << "0\n";
                return;
            }
        } else {
            for (int i = r; i < p; i++)
                ans *= 26, ans %= MOD;
        }
        r = p + len;
    }
    for (; r < n; r++)
        ans *= 26, ans %= MOD;
    cout << ans << "\n";
}
int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}