算法总结篇---KMP算法

写在前面
例题

写在前面

仅为自用，不做推广

一起来看猫片吧！

一篇不错的博客，然而我闷了一下午还是不会，看了看书算是搞懂了

博客里面各种性质讲的非常详细，有空可以回看一下

核心的两段代码

nxt数组预处理：

我这里使用pre表示nxt数组，用go表示要匹配的串

void init(){//预处理pre数组

	int len = strlen(go + 1);

	int j = 0;

	for(int i = 1; i < len; ++i){

		while(j > 0 && go[i + 1] != go[j + 1]) j = pre[j];

		if(go[i + 1] == go[j + 1]) ++j;

		pre[i + 1] = j;

	}

}

原字符串的匹配：

    for(int i = 0; i < len1; ++i){

		while(j > 0 && s[i + 1] != go[j + 1]) j = pre[j];

		if(s[i + 1] == go[j + 1]) ++j;

//		cout<<"i:"<<i<<" "<<j<<endl;

		if(j == len2){//如果匹配完成

			cnt++;

			j = 0;

		}

    }

例题

剪花布条

直接KMP匹配即可，匹配成功将匹配串的指针置为0

Radio Transmission

一个结论题，答案为 \(n - nxt[n]\)，好像与nxt数组本身的性质有关

OKR-Periods of Words

洛谷题解

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;

const int MAXN = 1e6+6;

const int INF = 1;

const int mod = 1;

int n;

LL ans = 0;

char s[MAXN];

int pre[MAXN];

int read(){

	int s = 0, f = 0;

	char ch = getchar();

	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();

	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();

	return f ? -s : s;

}

void init(){

	int j = 0;

	for(int i = 1; i <= n; ++i){

		while(j > 0 && s[i + 1] != s[j + 1]) j = pre[j];

		if(s[i + 1] == s[j + 1]) ++j;

		pre[i + 1] = j;

	}

}

int main()

{

	n = read();

	cin >> (s + 1);

	init();

	for(int i = 1; i <= n; ++i){

		int j = i;

		while(pre[j]) j = pre[j];

		if(pre[i]) pre[i] = j;

		ans += (i - j);

	}

	printf("%lld", ans);

	return 0;

}

似乎在梦中见过的样子

看这位大佬的题解

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;

const int MAXN = 2e4+6;

const int INF = 1;

const int mod = 1;

int n, k, cnt = 0;

char s[MAXN];

int pre[MAXN];

int read(){

	int s = 0, f = 0;

	char ch = getchar();

	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();

	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();

	return f ? -s : s;

}

void Kmp(int l){

	int j = l - 1;

	pre[l] = pre[l - 1] = j;

	for(int i = l; i < n; ++i){

		while(j > l - 1 && s[j + 1] != s[i + 1]) j = pre[j];

		if(s[j + 1] == s[i + 1]) j++;

		pre[i + 1] = j;

	}

	for(int i = l; i < n; ++i){

		j = pre[i + 1];

		while(j > l - 1 && l + 2 * (j - l + 1) > i + 1) j = pre[j];

		if(j - l + 1 >= k) cnt++;

	}

}

int main()

{

	cin >> (s + 1);

	k = read();

	n = strlen(s + 1);

	for(int i = 1; i <= n; ++i) Kmp(i);

	printf("%d", cnt);

	return 0;

}

Censoring

主要思路是开一个栈，来储存还未被消去的字符串

如果一个串匹配完成，从弹出相应的串

在入栈是顺便记录入栈字符的失陪位置，匹配完一个串后可以直接从栈顶所对字符的失陪位置开始匹配

从前到后跑一遍即可，复杂度 \(O(n)\)

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;

const int MAXN = 1e6+6;

const int INF = 1;

const int mod = 1;

char s[MAXN], t[MAXN];

int lens, lent;

int pre[MAXN], f[MAXN];

int stc[MAXN], sc = 0;

int read(){

	int s = 0, f = 0;

	char ch = getchar();

	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();

	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();

	return f ? -s : s;

}

void init(){

	int j = 0;

	for(int i = 1; i <= lent; ++i){

		while(j && t[i + 1] != t[j + 1]) j = pre[j];

		if(t[i + 1] == t[j + 1]) ++j;

		pre[i + 1] = j;

	}

}

int main()

{

	cin >> (s + 1);

	cin >> (t + 1);

	lens = strlen(s + 1);

	lent = strlen(t + 1);

	init();

	for(int i = 0, j = 0; i < lens; ++i){

		while(j && s[i + 1] != t[j + 1]) j = pre[j];

		if(s[i + 1] == t[j + 1]) ++j;

		f[i + 1] = j;

		stc[++sc] = i + 1;

		if(j == lent){

			sc -= lent, j = f[stc[sc]];

		}

	}

	for(int i = 1; i <= sc; i++){

		printf("%c", s[stc[i]]);

	}

	return 0;

}

巴特西