KMP

C:栗酱的数列

栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A'，满足

思路

将上述式子变形得到进而化简成 ，因此我们可以构造新的数组，使得,，用新的A数组匹配B数组。 此时，只需要对B数组跑一个next数组，利用KMP对A数组进行匹配即可。

样例

输入

1
2
3
4
5
6
7
2
3 2 5
7 8 7
8 7
3 2 5
7 8 9
8 7
输出
1
2
1
2
数据范围
1
2
3
T≤15,
2≤m≤n≤2×105,
1≤ai,bi,k≤109

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define pb push_back
#define endl "\n"

const LL mod = 1e9 + 7;
const LL N = 2e5 + 100;

LL a[N];
LL aa[N];
LL b[N];
LL bb[N];
int nxt[N];
LL t, n, m, x, y, k;

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

void getNext()
{
    for (int i = 2, j = 0; i <= m; i++)
    {
        while (j && bb[i] != bb[j + 1])
            j = nxt[j];
        if (bb[i] == bb[j + 1])
            j++;
        nxt[i] = j;
    }
}
void solve()
{
    cin >> n >> m >> k;
    memset(nxt, 0, sizeof nxt);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] %= k;
    }
    for (int i = 1; i < n; i++)
    {
        aa[i] = (a[i + 1] - a[i] + k) % k;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        b[i] %= k;
    }
    for (int i = 1; i < m; i++)
    {
        bb[i] = (b[i + 1] - b[i] + k) % k;
    }
    getNext();
    int ans = 0;
    if (m == 1)
        ans = n;
    for (int i = 1, j = 0; i < n; i++)
    {
        while (j && (aa[i] + bb[j + 1]) % k != 0)
            j = nxt[j];
        if ((aa[i] + bb[j + 1]) % k == 0)
        {
            j++;
        }
        if (j == m - 1)
        {
            j = nxt[j];
            ans++;
        }
    }
    cout << ans << endl;
}

int main()
{
    init();
    cin >> t;
    while (t--)
    {
        solve();
    }
}

D:K匹配

给定一个长度为n的字符串S和一个长度为k的字符串T，现在牛牛想知道S有多少个子串和T是满足k匹配的。(T能够在该子串至少匹配出一个)

思路

不难想到，可以用KMP在S里找到所有的T的位置。此时问题转化为，选择一个区间至少包含1一个目标区间的选择个数。对于区间选择，选择一个左边界和一个右边界。记录T在S的起始位置为，则T串所在区间为。不难发现，包含该区间的区间数为，当有另外一个区间时，它的选择会产生重复，根据容斥原理可知重复的部分为左边界的部分。为此，根据容斥原理最终计数应为

样例

输入

1
2
3
10 2
abaaaababa
ab
输出
1
33

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

const int MAX = 1e7 + 10;
long long n, k;
char s[MAX];
char t[MAX];
int nxt[MAX];

void getNext(char *str)
{
    for (int i = 2, j = 0; str[i]; i++)
    {
        while (j && str[i] != str[j + 1])
            j = nxt[j];
        if (str[i] == str[j + 1])
            j++;
        nxt[i] = j;
    }
}

long long get(long long len)
{
    return len * (len + 1) / 2;
}
int main()
{
    ios::sync_with_stdio(false);

    cin >> n >> k;
    cin >> s + 1;
    cin >> t + 1;
    getNext(t);

    vector<long long> v;
    v.push_back(0);
    for (int i = 1, j = 0; s[i]; i++)
    {
        while (j && s[i] != t[j + 1])
            j = nxt[j];
        if (s[i] == t[j + 1])
            j++;
        if (j == k)
        {
            v.push_back(i - k + 1);
            j = nxt[j];
        }
    }

    long long ans = 0;
    for (int i = 1; i < v.size(); i++)
    {
        ans += (v[i] - v[i - 1]) * (n - v[i] - k + 2);
    }
    cout << ans << endl;
}
build本页面最近更新：2022/7/12 15:32:00，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论