题目描述

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式
第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串S。

输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围
1≤N≤104
1≤M≤105

输入样例：

3
aba
5
ababa

输出样例：

0 2

算法1

(暴力枚举) $O(n^2)$

void kmp(const string& p, const string& s) {
    const int m = p.size();
    const int n = s.size();

    for(int i = 0; i < n; i++) {
        bool flag = true;
        for(int j = 0; j < m; j++) {
            if(s[i + j] == p[j]) 
               continue;
            flag = false;
            break;
        }
        if(flag) cout << i << ' ';
    }
}

时间复杂度 O(m + n)

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef vector<int> vec;

void init(string& s) {
    int n;
    cin >> n;
    char c;
    for(int i = 0; i < n; i++) {
        cin >> c;
        s.push_back(c);
    }
}

void kmp(const string& p, const string& s) {
    const int m = p.size();
    const int n = s.size();

    // i 前缀字符串的尾部下标，j 后缀字符串的尾部下标
    // i + 1 尝试匹配的字符的下标
    // 要使 i + 1 能从第一个字符开始，那么 i + 1 = 0，所以 i = -1
    // 由于i, j同时维护同一个字符串p，都指向第一个字符绝对相等
    // 可以直接跳过，所以 j 取值从 1 开始
    // 由于前缀的尾部指针 i 的初始值是 -1，索性将 next 数组全部初始化成 -1
    vec v(m, -1);   

    for(int i = -1, j = 1; j < m; j++) {
        // 前缀和后缀失配
        // 读取上一次恰好匹配时前缀字符串的尾部下标
        while(i >= 0 && p[i + 1] != p[j]) i = v[i];
        // 前缀和后缀恰好匹配，尝试下一对字符是否相等
        // 相等，则让前缀包含这个字符
        // 保存前缀和后缀匹配时前缀字符串的尾部下标
        if(p[i + 1] == p[j]) v[j] = ++i;
    }

    // i 模板串的下标，j 模式串的子串的尾部下标
    // i, j维护不同的字符串，第一个字符可能不同，所以j = 0
    for(int i = -1, j = 0; j < n; j++) {
        // 模式串的子串和模板串的子串失配
        // 读取上一次恰好匹配时模式串的子串的尾部下标
        while (i >= 0 && p[i + 1] != s[j]) i = v[i];
        // 模式串的子串和模板串的子串恰好匹配，尝试下一对字符是否相等
        // 相等，则让模式串的子串包含这个字符
        if (p[i + 1] == s[j]) i++;
        // 当模板串的指针移动到模板串的尾部时，
        // 模式串的子串和模板串完全一样，输出模式串的子串的起始下标
        if (i == m - 1) cout << j - i << ' ';
    }
    cout << endl;
}

int main() {
    string p, s;
    init(p), init(s);
    kmp(p, s);
    return 0;
}