题目描述(简略版)

输入字符串$A、B$,对于每一个询问$x$,求恰与$B$中前$x$个字符匹配的$A$的后缀个数.

样例

输入：

6 2 5
aabcde
ab
0
1
2
3
4

输出

4
1
1
0
0

算法1

(字符串哈希+二分) $O(NlogM+M+Q)$

预处理$A$、$B$的前缀哈希,枚举$A$的所有后缀,二分确定匹配长度.

时间复杂度

前缀哈希预处理时间$O(N+M)$,$A$后缀个数$O(N)$,每个后缀二分复杂度$O(logM)$,询问次数$Q$,总时间复杂度$O(NlogM+M+Q)$

C++ 代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
vector<ull> prime;
vector<ull> get_hash(string& s)
{
    //求字符串的前缀哈希
    vector<ull> res(s.length() + 1);
    res[0] = 0;
    for (int i = 1; i <= s.length(); i++)
        res[i] = res[i - 1] * 131 + (s[i - 1] - 'a');
    return res;
}
ull substr_hash(vector<ull>& hsh, int l, int r)
{
    //求子串的哈希值
    if (l > r)//空串直接返回零
        return 0;
    return hsh[r] - hsh[l - 1] * prime[r - l + 1];
}
int main()
{
    int len1, len2, q;
    cin >> len1 >> len2 >> q;
    string a, b;
    cin >> a >> b;
    vector<int> res(len2 + 1);
    res.resize(len2 + 1);//res[i]表示匹配长度为i的后缀个数
    prime.resize(max(len1, len2));//用于储存素数的幂
    prime[0] = 1;
    for (int i = 1; i < prime.size(); i++)//计算素数幂
        prime[i] = prime[i - 1] * 131;
    //计算A、B的前缀哈希
    vector<ull> hash1, hash2;
    hash1 = get_hash(a);
    hash2 = get_hash(b);
    for (int i = 1; i <= len1; i++)//枚举A的后缀
    {
        //二分法确定匹配长度
        int l = 0, m, r = len2;
        while (l < r)
        {
            m = (l + r + 1) / 2;
            //比较两个串长度为m的前缀,如果两者相等说明匹配长度不小于m
            if (substr_hash(hash1, i, i + m - 1) == substr_hash(hash2, 1, m))
                l = m;
            else
                r = m - 1;
        }
        res[l]++;//l即为匹配长度,统计答案
    }
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        //如果x比B的长度还大,一定没有后缀满足
        cout << (x <= len2 ? res[x] : 0) << endl;
    }
    return 0;
}

算法2

($KMP$匹配) $O(N+M+Q)$

用$num[i,j]$表示可作为$B$的前缀的以$A[j]$结尾的长度为$i$的$A$的子串个数,注意到每个这样的子串都可以扩展为匹配长度不小于$i$的后缀,而且对于固定的$i$和不同的$j$,这些后缀一定各不相同.因此$$\sum_{j=1}^N num[i,j]\overset{def}{=}sum[i]$$就是匹配长度不小于$i$的后缀个数,匹配长度恰为$i$的后缀个数即为$$sum[i]-sum[i+1]$$
以$A$为主串,$B$为模式串进行$KMP$匹配,在匹配过程中,假设$A$与$B$已经匹配的部分是$A[p_a-p_b+1:p_a]$和$B[1:p_b]$,长度为$p_b$,那么$A[p_a-p_b+1:p_a]$就是最长的可作为$B$的前缀的以$A[p_a]$结尾的$A$的子串,其长度为$p_b$,也就是$num[p_b,p_a]\+\+$.考虑$next$数组的性质,$$B[1:next[p_b]]=B[p_b-next[p_b]+1:p_b]$$因此$$A[p_a-next[p_b]+1:p_a]=B[p_b-next[p_b]+1:p_b]=B[1:next[p_b]]$$即$A[p_a-next[p_b]+1:p_a]$是最长的可作为$B$的前缀的以$A[p_a]$结尾的长度小于$p_b$的$A$的子串,其长度为$next[p_b]$,也就是$num[next[p_b],p_a]\+\+$.以此类推可以不断做下去,最终可以不重不漏地找到所有可作为$B$的前缀的以$A[p_a]$结尾的子串.在整个匹配过程中,$p_a$遍历了$A$,因此一趟匹配就可以求出$num$
但是这样做的时间复杂度和空间复杂度太大,需要加以优化.
(空间优化)首先注意到最终要获得的是$sum$,而$sum$是对$num$求和得到的,因此完全不需要开一个二维数组$num$,而可以直接在$sum$中进行统计,将$num[p_b,p_a]\+\+$变为$sum[p_b]\+\+$.
(时间优化)在上面的算法中,对于特定的$p_a$通过不断取$next$数组,每一个子串都被单独算了一遍.注意到对于每一个可作为$B$的前缀的长度为$p_b$的$A$的子串,对应地有一个可作为$B$的前缀的长度为$next[p_b]$的$A$的子串,而$sum$的计算并不区分$p_a$,因此对于每一个$p_a$,可以只统计长度为$p_b$的那个子串,当一趟匹配完成后,自顶向下地将所有比它短的衍生的子串求出.具体处理详见代码.

时间复杂度

$KMP$匹配过程时间复杂度$O(N+M)$,询问次数$Q$,总时间复杂度$O(N+M+Q)$

C++ 代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    string a, b;
    cin >> a >> b;
    b += '$';//加一个结束标志,简化KMP匹配过程
    vector<int> nxt(m + 1);//B的next数组
    vector<int> sm(m + 2);//sum数组,多开一个避免越界
    nxt[0] = -1;
    for (int i = 1; i <= m; i++)
    {
        //next数组计算
        int k = nxt[i - 1];
        while (k != -1 && b[k] != b[i - 1])
            k = nxt[k];
        nxt[i] = k + 1;
    }
    int pa = 0, pb = 0;//两个指针,分别指向A和B上待匹配的字符
    while (pa < n)
        if (pb == -1 || a[pa] == b[pb])
        {
            pa++;
            pb++;
            //每次更新pa后都需要统计sum数组
            sm[pb]++;
            //注意这里只统计最长的子串
            //其他由next数组获得的更短的子串在匹配结束后统一处理
        }
        else
            pb = nxt[pb];//匹配失败回溯
    for (int i = m; i > 0; i--)
        sm[nxt[i]] += sm[i];//自顶向下将之前未统计的子串也统计进去
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        //如果询问的长度比B的长度还大就直接输出0
        cout << (x <= m ? sm[x] - sm[x + 1] : 0) << endl;
    }
    return 0;
}