[Luogu p5410] [template] extend KMP (Z function) (string)

【 Templates 】 Expand KMP（Z function ）

Topic link ：luogu P5410

The main idea of the topic

Give you a string , I want you to ask each suffix to follow it LCP The length of .（Z function ）
Here are two strings , Ask you to find a string, each suffix with another string LCP The length of .（exKMP）

Ideas

This thing feels like a horse pulling a cart .

Consider knowing the current answer $z_{1\sim i-1}$, Consider how to ask for $z_i$.
First of all, we must find a matching string $[l,r]$, That must be looking for $r$ maximal , The record is currently $l,r$.

And then if $i⩽r$, We consider using it , Through proof, we can get $r_i⩾\min (r-i+1,r_{i-l+1})$
Proof considers bit by bit proof , set up $1⩽x⩽\min (r-i+1,r_{i-l+1})$
$s_{i+x-1}=s_{l+(i+x-l)-1}$
$=s_{1+(i+x-l)-1}=s_{i+x-l}$（ The restrictions on the left ）
$=s_{1+(i-l+1)+x}$
$=s_{1+x}$（ When $x\le z_{i-l+1}$）

Then we expand the violence , Then maintain the maximum $r$ For the $l,r$.
Then each number will only expand once , So the complexity is $O(n)$.

As for between two characters exKMP, We have the same matching method .

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

const int N = 2e7 + 5;
char a[N], b[N];
int an, bn, z[N], p[N];
ll ans;

void get_Z(char *s, int n) {
    
	for (int i = 1; i <= n; i++) z[i] = 0;
	z[1] = n;
	for (int i = 2, l = 0, r = 0; i <= n; i++) {
    
		if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
		while (i + z[i] <= n && s[i + z[i]] == s[1 + z[i]]) z[i]++;
		if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
	}
}

void exKMP(char *a, int n, char *b, int m) {
    
	for (int i = 1; i <= n; i++) p[i] = 0;
	for (int i = 1, l = 0, r = 0; i <= n; i++) {
    
		if (i <= r) p[i] = min(z[i - l + 1], r - i + 1);
		while (i + p[i] <= n && a[i + p[i]] == b[1 + p[i]]) p[i]++;
		if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
	}
}

int main() {
    
	scanf("%s", a + 1); scanf("%s", b + 1);
	an = strlen(a + 1); bn = strlen(b + 1);
	
	get_Z(b, bn);
	ans = 0; for (int i = 1; i <= bn; i++) ans ^= 1ll * i * (z[i] + 1); printf("%lld\n", ans);
	exKMP(a, an, b, bn);
	ans = 0; for (int i = 1; i <= an; i++) ans ^= 1ll * i * (p[i] + 1); printf("%lld", ans);
	
	return 0;
}