测试链接
题目描述
给出两个字符串 s 1 s_1 s1 和 s 2 s_2 s2，若 s 1 s_1 s1 的区间 [ l , r ] [l, r] [l,r] 子串与 s 2 s_2 s2 完全相同，则称 s 2 s_2 s2 在 s 1 s_1 s1 中出现了，其出现位置为 l l l。
现在请你求出 s 2 s_2 s2 在 s 1 s_1 s1 中所有出现的位置。
定义一个字符串 s s s 的 border 为 s s s 的一个非 s s s 本身的子串 t t t，满足 t t t 既是 s s s 的前缀，又是 s s s 的后缀。
对于 s 2 s_2 s2，你还需要求出对于其每个前缀 s ′ s' s′ 的最长 border t ′ t' t′ 的长度。
输入格式
第一行为一个字符串，即为 s 1 s_1 s1。
第二行为一个字符串，即为 s 2 s_2 s2。
输出格式
首先输出若干行，每行一个整数，按从小到大的顺序输出 s 2 s_2 s2 在 s 1 s_1 s1 中出现的位置。
最后一行输出 ∣ s 2 ∣ |s_2| ∣s2∣ 个整数，第 i i i 个整数表示 s 2 s_2 s2 的长度为 i i i 的前缀的最长 border 长度。
输入输出样例 #1
输入 #1
ABABABC
ABA输出 #1
1
3
0 0 1说明/提示
样例 1 解释
。
对于 s 2 s_2 s2 长度为 3 3 3 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 1 1 1。
数据规模与约定
本题采用多测试点捆绑测试，共有 4 个子任务。
- Subtask 0（30 points）： ∣ s 1 ∣ ≤ 15 |s_1| \leq 15 ∣s1∣≤15， ∣ s 2 ∣ ≤ 5 |s_2| \leq 5 ∣s2∣≤5。
- Subtask 1（40 points）： ∣ s 1 ∣ ≤ 1 0 4 |s_1| \leq 10^4 ∣s1∣≤104， ∣ s 2 ∣ ≤ 1 0 2 |s_2| \leq 10^2 ∣s2∣≤102。
- Subtask 2（30 points）：无特殊约定。
- Subtask 3（0 points）：Hack。
对于全部的测试点，保证 1 ≤ ∣ s 1 ∣ , ∣ s 2 ∣ ≤ 1 0 6 1 \leq |s_1|,|s_2| \leq 10^6 1≤∣s1∣,∣s2∣≤106， s 1 , s 2 s_1, s_2 s1,s2 中均只含大写英文字母。
题解
#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n;
int kmp[N];
int la,lb,j;
char a[N];
char b[N];
void solve()
{cin>>a+1;cin>>b+1;j=0;int la = strlen(a+1);int lb = strlen(b+1);for(int i=2;i<=lb;i++){while(j&&b[j+1]!=b[i])j = kmp[j];if(b[j+1]==b[i])j++;kmp[i]=j;}j = 0;for(int i=1;i<=la;i++){while(j&&b[j+1]!=a[i])j=kmp[j];if(b[j+1]==a[i])j++;if(j==lb){cout<>t;while(t--){solve();}return 0;
}