当前位置：首页 > backend >正文

洛谷-P3375 【模板】KMP

backend 2025/6/19 23:27:52

题目描述

给出两个字符串 s1 和 s2，若 s1 的区间 [l,r] 子串与 s2 完全相同，则称 s2 在 s1 中出现了，其出现位置为 l。
现在请你求出 s2 在 s1 中所有出现的位置。

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。
对于 s2，你还需要求出对于其每个前缀 s′ 的最长 border t′ 的长度。

输入格式

第一行为一个字符串，即为 s1。
第二行为一个字符串，即为 s2。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 s2 在 s1 中出现的位置。
最后一行输出 ∣s2∣ 个整数，第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。

输入输出样例

输入 #1复制运行

ABABABC
ABA

输出 #1复制运行

1
3
0 0 1

说明/提示

样例 1 解释

。

对于 s2 长度为 3 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 1。

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

Subtask 1（30 points）：∣s1∣≤15，∣s2∣≤5。
Subtask 2（40 points）：∣s1∣≤104，∣s2∣≤102。
Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 1≤∣s1∣,∣s2∣≤106，s1,s2 中均只含大写英文字母。

解题思路：

这里用的是kmp算法。也就是先确定s2的next数组，再在s1里面看有无s2字符串【kmp算法的优点在于它是一个线性查找O(m+n)】

先确定next数组：

vector<long long> build_next(string b){vector<long long> nexts;nexts.push_back(0);long long i=0,j=1;for(;j<b.size();){if(b[j]==b[i]){i++;j++;nexts.push_back(i);}else{if(i==0){j++;nexts.push_back(i);}else{i=nexts[i-1];}}}return nexts;
}

再跟据next数组线性查找s2字符串：

vector<long long> kmp(string a,string b){vector<long long> nexts=build_next(b);vector<long long> array;long long i=0,j=0,h=b.size();for(;j<a.size();){if(a[j]==b[i]){i++;j++;}else{if(i==0){j++;}else{i=nexts[i-1];}}if(i==h){array.push_back(j-i+1);i=nexts[i-1];}}return array;
}

总体代码：

#include<bits/stdc++.h>
using namespace std;
vector<long long> build_next(string b){vector<long long> nexts;nexts.push_back(0);long long i=0,j=1;for(;j<b.size();){if(b[j]==b[i]){i++;j++;nexts.push_back(i);}else{if(i==0){j++;nexts.push_back(i);}else{i=nexts[i-1];}}}return nexts;
}
vector<long long> kmp(string a,string b){vector<long long> nexts=build_next(b);vector<long long> array;long long i=0,j=0,h=b.size();for(;j<a.size();){if(a[j]==b[i]){i++;j++;}else{if(i==0){j++;}else{i=nexts[i-1];}}if(i==h){array.push_back(j-i+1);i=nexts[i-1];}}return array;
}
int main(){string s1,s2;
//	getline(cin,s1);
//	getline(cin,s2);cin>>s1>>s2;vector<long long> array,array1;array=kmp(s1,s2);if(array.size()){for(long long i=0;i<array.size();i++){cout<<array[i]<<endl;}}array1=build_next(s2);for(long long i=0;i<array1.size();i++){cout<<array1[i]<<" ";}return 0;
}

【！！！！这里string字符串输入只能用cin，不要用getline，具体我也不知道为什么有知道欢迎在评论区中解答！！！！]

查看全文

http://www.xdnf.cn/news/13775.html