$upd:2024.5.4$ https://www.cnblogs.com/qinyiting/p/17870833.html

题目描述

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

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

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

输入格式

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

第二行输入字符串 P。

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

第四行输入字符串 S。

输出格式

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

数据范围

1≤N≤105
1≤M≤106

输入样例：

3
aba
5
ababa

输出样例：

0 2

C++代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;   // n 子串 p 长度， m 父串 s 长度
int ne[N];  // next数组
char s[M], p[N];    // s 父串 p 子串

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;// 输入 （s,p 下标从1开始）

    // 求 next 数组：
    for (int i = 2, j = 0; i <= n; i ++ )   // next[1] = 0; 从2开始枚举
    {
        while (j && p[i] != p[j + 1]) j = ne[j];    //匹配不成功 回溯
        if (p[i] == p[j + 1]) j ++ ;                // 匹配成功 j ++；
        ne[i] = j;                                  // 赋值
    }
    /*
        匹配 1 后面长度为 j 的串 和 i 前面长度为 j 的串
        i为后缀最后一位
        j为前缀最后一位

        如果不一样 就回溯
        如果一样 就 j ++ 扩大前后缀长度
    */


    // 匹配 
    for (int i = 1, j = 0; i <= m; i ++ )        // 错位比较： i 与 j + 1 比较
    {
        while (j && s[i] != p[j + 1]) j = ne[j]; // 匹配不成功 回溯
        if (s[i] == p[j + 1]) j ++ ;             // 匹配成功 继续匹配
        if (j == n) //如果匹配成功
        {
            printf("%d ", i - n); 
            // 原为 i - n + 1 因 题目中串以0开头 程序中串以1开头 省
            j = ne[j];                           // 回溯 继续匹配 
        }
    }
    /*
        模式匹配子串父串
        不断后移 bf算法优化
        复杂度o(n)
    */

    return 0;
}

时间复杂度

O(n)