子串匹配

时间限制：1 秒
空间限制：256M

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

---

题目描述

给定文本串 $S_1$ 和模式串 $S_2$，若存在下标 $l(1\le l\le |S_1|-|S_2|+1)$ 使得 $S_1[l\dots l+|S_2|-1]=S_2$，则称 $S_2$ 在 $S_1$ 中出现，出现位置为 $l$（下标从 $1$ 开始）。

你的任务包括两部分：

• 输出 $S_2$ 在 $S_1$ 中的所有出现位置（按升序）；
• 对于 $S_2$ 的每个前缀 $P_i=S_2[1\dots i]$，求其最长 border 的长度。这里 border 指既是 $P_i$ 的前缀又是后缀、长度严格小于 $|P_i|$ 的非空子串。

---

输入描述

输入共两行：

• 第一行输入文本串 $S_1(1\le |S_1|\le 10^6)$；
• 第二行输入模式串 $S_2(1\le |S_2|\le 10^6)$。

两串均由大小写英文字母组成。

---

输出描述

首先按升序逐行输出 $S_2$ 在 $S_1$ 中的出现位置（若无出现则输出为空行）。

最后一行输出 $|S_2|$ 个整数，第 $i$ 个整数表示前缀 $P_i$ 的最长 border 长度，数之间以单个空格分隔。

---

示例 1

输入：

ABABABC
ABA

输出：

1
3
0 0 1

说明： 出现位置为 $1$、$3$；对于前缀边界数组：$A\Rightarrow 0$，$AB\Rightarrow 0$，$ABA\Rightarrow 1$。

---

示例 2

输入：

AAA
AA

输出：

1
2
0 1

说明： 出现位置为 $1$、$2$；前缀 border 长度序列为 $[0,1]$。

---

数据范围与提示

• $1\le |S_1|\le 10^6$
• $1\le |S_2|\le 10^6$
• 字符集为大小写英文字母
• 核心思路：本题是 KMP 的模板变形，两部分可以共用同一份前缀函数（next 数组）：
  1. 先对模式串 $S_2$ 求前缀函数 $\pi [i]$，其含义即为「前缀 $P_i$ 的最长 border 长度」，直接就是第二问的答案；
  2. 再用 $S_2$ 对文本串 $S_1$ 做 KMP 匹配，每当匹配长度达到 $|S_2|$ 时，出现位置为 $i-|S_2|+2$（转换为 1 起始下标），随后按 $\pi$ 数组回退继续匹配。
• 时间复杂度 $O(|S_1|+|S_2|)$，空间复杂度 $O(|S_2|)$。注意输入规模较大，建议使用按行读取的快速输入方式。

解题思路

本题是 KMP 算法的模板变形题，要求完成两个任务：

1. 找出模式串 $S_2$ 在文本串 $S_1$ 中的所有出现位置（1-based 下标）；
2. 对于 $S_2$ 的每个前缀 $P_i=S_2[1\dots i]$，求其最长 border 的长度（border 指既是前缀又是后缀、长度严格小于 $|P_i|$ 的非空子串）。

这两个任务都可以通过 KMP 算法中的前缀函数（$\pi$ 数组） 高效完成。

1. 问题等价转化

• 前缀函数：对于模式串 $S_2$，定义 $\pi [i]$ 表示子串 $S_2[0\dots i]$ 的最长 border 长度。这恰好就是题目第二问所要求的答案，因此只需对 $S_2$ 求一次前缀函数即可。
• 模式匹配：在文本串 $S_1$ 上运行 KMP 匹配过程，维护当前已匹配的长度 $j$。当 $j$ 达到 $|S_2|$ 时，说明在 $S_1$ 中找到了一个完整的 $S_2$，其起始位置（1-based）为 i - |S_2| + 2（因为 i 是当前在 $S_1$ 中的 0-based 下标）。记录该位置后，令 j = π[j-1] 继续匹配，以寻找可能的重叠出现。

2. 算法实现

1. 求前缀函数 π：
   • 初始化 π 数组大小为 |S_2|，全部为 0。
   • 令 j = 0，从 i = 1 遍历到 |S_2| - 1：
     • 当 j > 0 且 S_2[i] != S_2[j] 时，回退 j = π[j-1]。
     • 若 S_2[i] == S_2[j]，则 j++。
     • 记录 π[i] = j。
2. KMP 匹配：
   • 令 j = 0，从 i = 0 遍历到 |S_1| - 1：
     • 当 j > 0 且 S_1[i] != S_2[j] 时，回退 j = π[j-1]。
     • 若 S_1[i] == S_2[j]，则 j++。
     • 当 j == |S_2| 时，输出位置 i + 2 - |S_2|（1-based），然后令 j = π[j-1] 继续匹配。
3. 输出前缀函数：最后一行按顺序输出 π[0] 到 π[|S_2|-1]，用空格分隔。若 $S_2$ 在 $S_1$ 中无出现，则第一行输出空行（代码中未显式输出空行，但按题意若无匹配则没有位置输出，直接输出前缀函数行即可）。

3. 复杂度分析

• 时间复杂度：求前缀函数和 KMP 匹配均为线性扫描，总时间复杂度 $O(|S_1|+|S_2|)$。字符串长度最大 $10^6$，完全可行。
• 空间复杂度：仅需存储前缀函数数组，大小 $O(|S_2|)$，空间消耗很小。

总结

本题是 KMP 算法的直接应用，通过一次前缀函数计算同时解决了前缀 border 查询和模式匹配两个问题。代码简洁高效，充分利用了 KMP 的线性时间特性，适合处理长达 $10^6$ 的字符串。注意输入规模较大，使用 ios::sync_with_stdio(0) 加速输入输出即可。

代码简要说明

• 读入文本串 s1 和模式串 s2。
• 创建 vector<ll> kmp，大小与 s2 相同，用于存储前缀函数。
• 求前缀函数：j 为当前匹配长度，遍历 s2 从下标 1 开始，按 KMP 规则更新 j 并记录 kmp[i]。
• KMP 匹配：j 重置为 0，遍历 s1，按规则匹配。当 j == s2.size() 时，输出起始位置 i + 2 - s2.size()，并回退 j = kmp[j-1]。
• 最后遍历 kmp 数组，输出每个前缀的最长 border 长度。

代码内容

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

#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

string s1;
string s2;
vector<ll> kmp;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s1>>s2;
    kmp.resize((ll)s2.size());
    ll j=0;
    for(ll i=1;i<(ll)s2.size();i++)
    {
        while(j&&s2[i]!=s2[j]) j=kmp[j-1];
        if(s2[i]==s2[j]) j++;
        kmp[i]=j;
    }
    j=0;
    for(ll i=0;i<(ll)s1.size();i++)
    {
        while(j&&s1[i]!=s2[j]) j=kmp[j-1];
        if(s1[i]==s2[j])
        {
            j++;
            if(j==(ll)s2.size())
            {
                cout<<i+2-(ll)s2.size()<<'\n';
                j=kmp[j-1];
            }
        }
    }
    for(const auto& x:kmp) cout<<x<<' ';
    return 0;
}