KMP + Z函数基本概念入门水题

KMP
Z函数 | 拓展KMP

kmp

字符串 abcabcd 的前缀函数为 0 0 0 1 2 3 0 ，
字符串 aabaaab的前缀函数为 0 1 0 1 2 2 3 .
以第 i 个作为结尾和前缀匹配最多往前匹多长

Z函数

已第i个作为开始和前缀匹配往后面最长匹配多少

洛谷板子题 kmp 找位置

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 10;

int nxt[maxn];
char s1[maxn], s2[maxn];

void get_nxt(int n, char *s){
    memset(nxt, 0, (n + 5) * sizeof(int));
    nxt[0] = -1;
    int i = 0, j = -1;
    while(i < n){
        if(j == -1 || s[j] == s[i]){
            i++, j++;
            nxt[i] = j;
        }
        else j = nxt[j];
    }
}

void kmp(int n, int m) {
	int t1 = 0, t2 = 0;
	while(t1 < n) {
		if(t2 == -1 || s1[t1] == s2[t2]) t1 ++, t2 ++;
		else t2 = nxt[t2];
		if(t2 == m) {
			printf("%d\n", t1 - m + 1);
			t2 = nxt[t2]; // t2 = 0 不重复用的输出
		}
	}
}

int main() {
	scanf("%s %s", s1, s2);
	int n, m;
	n = strlen(s1), m = strlen(s2);
	get_nxt(m, s2);
	kmp(n, m);
	for(int i = 1; i <= m; i ++) printf("%d ", nxt[i]);
	puts("");
	return 0;
}

kmp 找循环节

POJ 2406

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 10;

int nxt[maxn];
char s[maxn];
int n;

void get_nxt(){
    memset(nxt, 0, (n + 5) * sizeof(int));
    nxt[0] = -1;
    int i = 0, j = -1;
    while(i < n){
        if(j == -1 || s[j] == s[i]){
            i++;
            j++;
            nxt[i] = j;
        }
        else
            j = nxt[j];
    }
}

int main() {
	while(scanf("%s", s) && s[0] != '.') {
		n = strlen(s);
		get_nxt();
		if(n % (n - nxt[n]) != 0) puts("1");
		else printf("%d\n", n / (n - nxt[n]));
	}
	return 0;
}

kmp 找所有循环节周期

POJ 1961

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 10;

int nxt[maxn];
char s[maxn];
int n;

void get_nxt(){
    memset(nxt, 0, (n + 5) * sizeof(int));
    nxt[0] = -1;
    int i = 0, j = -1;
    while(i < n){
        if(j == -1 || s[j] == s[i]){
            i++, j++;
            nxt[i] = j;
        }
        else j = nxt[j];
    }
}

int main() {
	int cas = 1;
	while(scanf("%d", &n) && n) {
	
		scanf("%s", s);
		get_nxt();
		printf("Test case# %d\n", cas ++);
		for(int i = 1; i <= n; i ++) {
			int k = i - nxt[i];
			if(i % k == 0 && i != k) printf("%d %d\n", i, i/k);
		}	puts("");
	}
	return 0;
}

Z 函数

Codeforces 126B Password

你要在一个串中找到“密码”，密码定义为既是前缀，也是后缀，同时在串中间出现过的子串。
i + z[i] == n i位开始能匹配到的后缀同时 ma >= n - i 之前出现过不小它的串

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
 
int z[maxn];
string s;
int n;
 
void get_z() {
	int l=0,r=0;
	for (int i=1; i<n; i++) {
		if (i>r) {
			l=i,r=i;
			while (r<n && s[r-l]==s[r]) r++;
			z[i]=r-l,r--;
		} else {
			int k=i-l;
			if (z[k]<r-i+1) z[i]=z[k];
			else {
				l=i;
				while (r<n && s[r-l]==s[r]) r++;
				z[i]=r-l,r--;
			}
		}
	}
}
 
int main() {
	cin >> s;
	n = s.size();
	get_z();
	int pos = -1, ma = 0;
	for(int i = 1; i < n; i ++) {
		if(z[i] + i == n && ma >= n - i) {
			pos = i;
			break;
		}
		ma = max(ma, z[i]);
	}
 
// for(int i = 1; i < n; i ++) {
// cout << z[i] << " ";
// }
// cout << endl;
// cout << pos << " " << ma << endl;
	if(pos == -1) cout << "Just a legend";
	else for(int i = 0; i < n - pos; i ++) cout << s[i];
	cout << endl;
	return 0;
}

Codeforces 535D Tavas and Malekas

每个位置如果不与之前重合直接放就行
重合判断能不能合法放进去
用差分标记最后0得位置就是26 ^ 多少

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;

int z[maxn], pos[maxn], a[maxn];
string s;
int n, m, l;

void get_z(int n) {
	int l=0,r=0;
	for (int i=1; i<n; i++) {
		if (i>r) {
			l=i,r=i;
			while (r<n && s[r-l]==s[r]) r++;
			z[i]=r-l,r--;
		} else {
			int k=i-l;
			if (z[k]<r-i+1) z[i]=z[k];
			else {
				l=i;
				while (r<n && s[r-l]==s[r]) r++;
				z[i]=r-l,r--;
			}
		}
	}
}

bool chk(int i, int j) {
	if(i + l <= j) return 1;
	return z[j - i] >= i + l - j;
}

int ksm(int a, int b) {
	int res = 1;
	for(; b; b >>= 1) {
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
	}
	return res;
}

signed main() {
	cin >> n >> m;
	cin >> s;
	l = s.size();
	get_z(l);
	for(int i = 1; i <= m; i ++) cin >> pos[i], pos[i]--;

	for(int i = 1; i < m; i ++) {
		if(chk(pos[i], pos[i + 1])) {
			a[pos[i]] ++, a[pos[i] + l] --;
		} else {
			cout << 0 << endl;
			return 0;
		}
	}
	if(m) a[pos[m]] ++, a[pos[m] + l] --;
	for(int i = 1; i < n; i ++) 
		a[i] += a[i - 1];
	
	int tot = 0;
	for(int i = 0; i < n; i ++) if(!a[i]) tot ++;
	cout << ksm(26, tot) << endl;
	return 0;
}

KMP + Z函数 基本概念 入门水题

kmp