题目描述

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

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

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

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

第二行输入字符串P。

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

第四行输入字符串S。

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

数据范围
$1≤N≤10^4$
$1≤M≤10^5$

输入样例：

3
aba
5
ababa

输出样例：

0 2

算法1

(暴力枚举) $O(nm)$

C++ 代码

#include <iostream>

using namespace std;

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

char p[N], s[M];

int n, m;

int main()
{
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1; 

    for(int i = 1; i <= m; i ++) // 暴力枚举 会TLE
    {
        int j = 1, k = i;
        while(j <= n && s[k ++] == p[j ++]);
        if(n == j - 1) printf("%d ",i - 1);
    }

    return 0;
}

算法2

(KMP) $O(n^2)$

C++ 代码

#include <iostream>

using namespace std;

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

int n, m;

char p[N], s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;



// 求next数组过程    
    for(int i = 2, j = 0; i <= n; i ++) // 初始的ne[1]是0所以 j = 0, 从第二个开始看所以 i = 2.
    {// j 此时表示ne[i - 1] 最终 j 要表示 ne[i];

        while(j && p[i] != p[j + 1]) j = ne[j]; // 若 j 有意义 且情况1不成立 则执行操作2
        if(p[i] == p[j + 1]) j ++; //若情况1成立则将当前的 ne[i - 1] 即 j 加上 1； 
        ne[i] = j;

      // j 此时表示了ne[i] 下次循环时 i ++ 再次进入时又表示了ne[i - 1] 
    }



 //匹配过程
    for(int i = 1, j = 0; i <= m; i ++) // i 表示长串的字符 j 表示短串的字符  都从 1 开始比较 p串总比较 j + 1 位
    {
        while(j && s[i] != p[j + 1]) j = ne[j]; // 若 p 串还可退 且当前匹配失败 则以ne数组为算法 后退
        if(s[i] == p[j + 1]) j ++; // 当前相等则预比较下一位 先将p串的指针向后移一位
        if(j == n)
        {   
            printf("%d ",i - n);
            j = ne[j];
        } // 如果当前匹配成功 则依照题目逻辑输出 且为寻找下一次做好准备
    }
}