字符串匹配

字符串匹配

时间限制：1 sec

空间限制：256 MB

问题描述

给定一个大串 A 和一个模式串 B，求 B 在 A 的哪些位置出现（输出这些出现位置的起始位置，下标从 0 开始）。

输入格式

第一行一个正整数 n，表示串 A 的长度。第二行包含一个长度为 n 的串 A。

第三行一个正整数 m，表示串 B 的长度。第四行包含一个长度为 m 的串 B。

保证串 A,B 只包含小写字母。

输格式

对于每个 B 在 A 中出现的位置，输出单独一行一个整数表示该次出现的起始位置。对于所有的这些位置，请升序（从小到大）输出。

样例输入

样例输

数据范围

对于 60% 的数据，保证 m<=10。

对于另外 20% 的数据，保证 A 的每一位在所有小写字母中等概率随机，且 B 为 A 中截取的一段。

对于 100% 的数据，保证 n<=500,000，m<=100,000。

提示

[此题是单模匹配算法的练习题。]

[可以尝试暴力匹配、KMP 算法、Boyer-Moore 算法、Rabin-Karp 算法，并比较它们的效果。]

代码

#include <bits/stdc++.h> using namespace std;

// ================= 代码实现开始 =================

vector<int> Next;

// 这是匹配函数，将所有匹配位置求出并返回

// n：串 A 的长度

// A：题目描述中的串 A

// m：串 B 的长度

// B：题目描述中的串 B

// 返回值：一个 vector<int>，从小到大依次存放各匹配位置vector<int> match(int n, string A, int m, string B) {

Next.resize(m);

int j = Next[0] = -1;

for (int i = 1; i < m; ++i) {

while (j >= 0 && B[i] != B[j + 1])

j = Next[j];

if (B[i] == B[j + 1])

++j;

Next[i] = j;

}

j = -1;

vector<int> ans;

for (int i = 0; i < n; ++i) {

while (j >= 0 && A[i] != B[j + 1])

j = Next[j];

if (A[i] == B[j + 1])

++j;

if (j == m - 1)

ans.push_back(i - m + 1);

}

return ans;

}

// ================= 代码实现结束 =================

int main() {

    ios::sync_with_stdio(false);

    int n, m;

    string A, B;

    cin >> n >> A;

    cin >> m >> B;

    vector<int> ans = match(n, A, m, B);

    for (vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)

        cout << *it << '\n';

    return 0;

}