题目描述

给定一个模式串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
a
6
abaaaa

输出样例：

0 2 3 4 5

样例

2
aa
6
abaaaa

输出样例：

2 3 4

算法1：暴力枚举

$O(nm)$

略

算法2：KMP

算法初衷：基于先前已匹配的模式串前缀，直接确定当前位置应该与模式串的哪个合适的最大位置进行匹配。

算法本质：将模式串和字符串匹配问题转化为求字符串各个位置i的“KMP-i后缀”问题。

定义-1：（个人定义）
i后缀：字符串A的所有子串里面以A[i]作为结尾的子串
真i后缀：字符串A的所有子串里面以A[i]作为结尾且不包含A首位置字符的子串
KMP-i后缀：字符串A的所有i后缀里面与模式串P的某个前缀相同的那些i后缀
KMP-真i后缀：字符串A的所有真i后缀里面与模式串P的某个前缀相同的那些真i后缀
KMP-最长i后缀：KMP-i后缀里面长度最长的i后缀
KMP-最长真i后缀：KMP-真i后缀里面长度最长的真i后缀

引理-1-1：

对于长度为n的模式串P和长度为m（0<n<=m）的字符串A：
    A[i - n + 1 ~ i] == P <=>  A的KMP-最长i后缀 == P

根据定义，引理的左右两边可以相互推导。

根据该引理，则字符串匹配问题可以通过求解A的KMP-最长i后缀进行解决。

时间复杂度

$O(m + n)$

KMP实现2-1：匹配 next[i - 1] + 1

j = next[i - 1]，判断 s[i] == p[j + 1]

字符串匹配方法：第 i - 1 匹配了 next[i - 1], 接下来比较 i 是否匹配 next[i - 1] + 1

next[]计算方法：根据next[i - 1]，计算next[i]

理论分析

定义-2：

next[]数组

1始下标：next[i] = 模式串自身KMP-最长真i后缀的长度

0始下标：next[i] = 模式串自身KMP-最长真i后缀的长度 - 1

引理-2-1：（参见李煜东书证明）

按照定义-2，1始下标模式串自身KMP-真i后缀的长度按照大小排序为：
    next[i] > next[next[i]] > next[next[next[i]] > ...

根据引理-2-1可以得出1始下标的next计算方法：

通过next[i-1]求next[i]

if p[i] == p[next[i - 1] + 1] : next[i] = next[i - 1] + 1
elif p[i] == p[next[next[i - 1]] + 1] : next[i] = next[next[i - 1]] + 1
...

边界条件：
1. 和模式串的首个字符仍不匹配
2. 匹配了模式串的所有字符

神奇的是，上面计算方法实际上对于下标从0或1开始都是适用的。

参考文献

《算法竞赛进阶指南》,李煜东
闫学灿 视频

C++ 代码

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
char p[N], s[M];


int kmp_idx1_lyd()
{
    int ne[N] = {0,0};

    for (int i = 2, j = 0; i <= n; i ++ )               // j = next[i - 1]
    {
        while (j > 0 && p[i] != p[j+1]) j = ne[j];      // p[i] != p[next[i - 1] + 1]
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++)                // j + 1 = p 首字符位置
    {
        while (j > 0 && s[i] != p[j + 1]) j = ne[j];    // s[i] != p[next[i - 1] + 1]
        if (s[i] == p[j + 1]) j ++;
        if (j == n)
        {
            j = ne[n];
            printf("%d ", i - n);
        }
    }

    return 0;

}


int kmp_idx0_lyd()
{
    int ne[N] = {-1};

    for (int i = 1, j = -1; i < n; i ++ )               // j = next[i - 1]
    {
        while (j > -1 && p[i] != p[j + 1]) j = ne[j];   // p[i] != p[next[i - 1] + 1]
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < m; i ++)                // j + 1 = p 首字符位置
    {
        while (j > -1 && s[i] != p[j + 1]) j = ne[j];   // s[i] != p[next[i - 1] + 1]
        if (s[i] == p[j + 1]) j ++;
        if (j == n - 1)
        {
            j = ne[n - 1];
            printf("%d ", i - n + 1);
        }
    }

    return 0;

}

int kmp_idx1()
{

    cin >> n >> p + 1 >> m >> s + 1;
    return kmp_idx1_lyd();

}

int kmp_idx0()
{

    cin >> n >> p >> m >> s;
    return kmp_idx0_lyd();
}

int idx_begin_with_0 = 0;

int main()
{
    if (idx_begin_with_0)
        kmp_idx0();
    else
        kmp_idx1();
}

KMP实现2-2：匹配 next[i]

j = next[i]，判断 s[i] == p[j]

字符串匹配方法：第 i - 1 匹配了 next[i - 1], 接下来比较 i 是否匹配 next[i]

next[]计算方法：根据next[i]，计算next[i + 1]

理论分析

定义-3：（十分烧脑）

next[]数组

0始下标：next[i] = 模式串自身KMP-最长真i-1后缀的长度

1始下标：next[i] = 模式串自身KMP-最长真i-1后缀的长度 + 1

引理-3-1 ：（未证明）

按照定义-3，0始下标模式串自身KMP-真i-1后缀的长度按照大小排序为：
    next[i] > next[next[i]] > next[next[next[i]] > ...

根据引理-3-1可以得出0始下标的next计算方法：

通过next[i]求next[i + 1]

if p[i] == p[next[i]] : next[i + 1] = next[i] + 1
elif p[i] == p[next[next[i]]] : next[i + 1] = next[next[i]] + 1
...

边界条件：
1. 和模式串的首个字符仍不匹配
2. 匹配了模式串的所有字符

神奇的是，上面计算方法实际上对于下标从0或1开始都是适用的。

参考文献

《数据结构》,严蔚敏

C++ 代码

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
char p[N], s[M];


int kmp_idx1_ywm()
{
    int ne[N] = {0,0};

    for (int i = 1, j = 0; i <= n - 1; i ++ )           // j = next[i]
    {
        while (j > 0 && p[i] != p[j]) j = ne[j];        // p[i] != p[next[i]]
        ne[i + 1] = j + 1;                              
        j ++;
    }

    for (int i = 1, j = 1; i <= m; i ++)                // j = 首字符位置
    {
        while (j > 0 && s[i] != p[j]) j = ne[j];        // s[i] != p[next[i]]
        if (j == n && s[i] == p[j])
        {
            // j = ne[j - 1] + 1 ;  // wrong
            j = ne[n];
            printf("%d ", i - n);
            // cout << ne[j] << ne[j - 1] + 1 << endl;
        }
        j ++;
    }
    return 0;
}

int kmp_idx0_ywm()
{
    int ne[N] = {-1};

    for (int i = 0, j = -1; i < n - 1; i ++ )           // j = next[i]
    {
        while (j != -1 && p[i] != p[j]) j = ne[j];      // p[i] != p[next[i]]
        ne[i + 1] = j + 1;
        j ++;
        // if (p[i + 1] == p[i]) ne[i + 1] = ne[j];
    }

    for (int i = 0, j = 0; i <= m; i ++)                // j = 首字符位置
    {
        while (j != -1 && s[i] != p[j]) j = ne[j];      // s[i] != p[next[i]]

        if (j == n - 1 && s[i] == p[j])
        {
            j = ne[n - 1];
            printf("%d ", i - n + 1);
        }
        j ++;
    }

    return 0;
}

int kmp_idx0_ywm2()
{
    int ne[N] = {-1};

    for (int i = 0, j = -1; i <= n - 1; i ++ )
    {
        while (j != -1 && p[i] != p[j]) j = ne[j];
        j ++;
        ne[i + 1] = j;
        // if (p[i + 1] == p[i]) ne[i + 1] = ne[j];
    }

    for (int i = 0, j = 0; i <= m; i ++)
    {
        while (j != -1 && s[i] != p[j]) j = ne[j];
        j ++;
        if (j == n)
        {
            j = ne[n];
            // j = ne[n - 1] + 1;
            printf("%d ", i - n + 1);
        }
    }

    return 0;
}




int kmp_idx1()
{

    cin >> n >> p + 1 >> m >> s + 1;
    return kmp_idx1_ywm();

}

int kmp_idx0()
{

    cin >> n >> p >> m >> s;
    return kmp_idx0_ywm();
}

int idx_begin_with_0 = 0;

int main()
{
    if (idx_begin_with_0)
        kmp_idx0();
    else
        kmp_idx1();
}