KMP板子题求调

问题讨论区 提高段
1

最近在学KMP
题目：https://www.luogu.com.cn/problem/P3375

#include<bits/stdc++.h>
using namespace std;
vector<int>get_next(string s){
	int i=0,j=-1;
	vector<int>a;
	a.push_back(-1);
	while(i<s.size()-1){
		if(j==-1||s[i]==s[j]){
			i++;j++;
			a.push_back(j);
		}else j=a[j];
	}return a;
}int main(){
	string a,b;
	vector<int>next;
	int p=0,q=-1;
	cin>>a>>b;
	next=get_next(b);
	p=0;
	for(int i=0;i<a.size();i++){
		bool f=1;
		for(int j=p;j<b.size();j++)
			if(a[i]!=b[j]){
				p=next[j];
				f=0;
				break;
			}
		if(f)cout<<i+1<<'\n';
	}for(int i:next)cout<<i<<" ";
	return 0;
}
2

%%%orz

3

不是我也才刚学KMP啊

4

额，你的get_next函数应该是写错了

（偷推人机KMP学习笔记

5

不对等等，你的KMP部分好像也写错了,你这样写复杂度还是会退化成 O(nm) 的

6

那要怎么改？

7

e你这个是自学的吗，感觉没见过长这样的 KMP…

你这个 while+vector 写的感觉挺奇怪的，爱莫能助，我给自己的代码加一个注释你看看吧。

#include<bits/stdc++.h>
using namespace std;
int n,m,p[1000001];
char s1[1000001],s2[1000001];
int main(){
	scanf("%s%s",s1 + 1,s2 + 1);//1 下标 
	n = strlen(s1 + 1),m = strlen(s2 + 1);
	for(int i = 2,j = 0;i <= m;i ++){//i 表示当前要找 s2_{1...i} 的真 border, 长度为 1 的前缀真子串长度为 0 所以从 2 开始 
		//每一轮开始之前，j 保存了 s2_{1...i-1} 的最长真 border 长度，这意味着 s2_{1...j}=s2_{i-j...i-1} 
		while(j && s2[i] != s2[j + 1]) j = p[j]; 
		if(s2[i] == s2[j + 1]) j ++; //如果 s2_{j+1}=s2_i，加上上面条件就可以确认 s2_{1...i} 的最长 border 长度为 j+1；否则要 while 循环减少 j 
		p[i] = j;//为什么 while 循环中是 j=p_j？因为我们不仅要求 s2_{j+1} 和 s2_i 相等，还要求 s2_{1...j}=s2_{i-j...i-1}，而 border 是有传递性的， 
	}// p_j 是 j 的 border，j 是 i-1 的 border，那么 p_j 也是 i-1 的 border。 
	for(int i = 1,j = 0;i <= n;i ++){
		while(j && s1[i] != s2[j + 1]) j = p[j];
		if(s1[i] == s2[j + 1]) j ++; 
		if(j == m){
			printf("%d\n",i - m + 1);
			j = p[j];
		}
	}
	for(int i = 1;i <= m;i ++) printf("%d ",p[i]);
	return 0;
}
8

谢谢