F04 扩展 KMP(Z 函数)

// 模板】扩展 KMP（Z 函数）
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1e6 + 5;
char t[N], s[N];
int z[N], p[N];

void get_z(char *s, int n)
{
	z[1] = n;
	for (int i = 2, l, r = 0; i <= n; i++)
	{
		if (i <= r)z[i] = min(z[i - l + 1], r - i + 1);
		while (s[1 + z[i]] == s[i + z[i]])z[i]++;
		if (i + z[i] - 1 > r)l = i, r = i + z[i] - 1;
	}
}
void get_p(char *s, int n, char *t, int m)
{
	for (int i = 1, l, r = 0; i <= m; i++)
	{
		if (i <= r)p[i] = min(z[i - l + 1], r - i + 1);
		while (1 + p[i] <= n && i + p[i] <= m && s[1 + p[i]] == t[i + p[i]])p[i]++;
		if (i + p[i] - 1 > r)l = i, r = i + p[i] - 1;
	}
}
int main()
{
	scanf("%s%s", t + 1, s + 1);
	int m = strlen(t + 1), n = strlen(s + 1);
	get_z(s, n);
	get_p(s, n, t, m);

	for(int i=1;i<=m;i++)printf("%d ", p[i]);
	return 0;
}

hansang 的注释版代码：

#include<bits/stdc++.h> 
using namespace std;

typedef long long LL;
const int N = 1e6 + 10; 
char sa[N], sb[N];    
LL z[N], p[N];          // z: sb 的 Z 函数数组, p: EXKMP 数组
int lena, lenb;

// 计算文本串 sb 的 Z 函数
// z[i] 表示 sb[i..lenb]与 sb[1..lenb] 的最长公共前缀长度（LCP） 
void get_z() {
	memset(z, 0, sizeof(z)); 
    z[1] = lenb;  // 特殊情况：sb[1..lenb]与自身的 LCP 就是整个字符串长度
    
    // 初始化最右匹配区间 [l, r]
    // 这区间就是 sb[l..r] = sb[1..r - l + 1]
    // l、r: 当前已知最右匹配区间的左端点和右端点
    for (int i = 2, l = 0, r = 0; i <= lenb; i ++) {
    	// i 从 2 开始，代表后缀开始的位置，l = r = 0，一开始并没有区间 
        // 如果 i 在当前最右匹配区间 [l, r] 内
        if (i <= r) {
            z[i] = min(z[i - l + 1], 1LL * (r - i + 1));
            // 根据定义 1 到 r - l + 1 和 l 到 r 是相等 的
			// 所以 i - l + 1 到 r - l + 1 和 i 到 r 是相等的
			// 因此以 i - l + 1 为标准，最大 LCP 最多就可以取 r - i + 1
			// 但是如果这个 r - i + 1 比 z[i - l + +1] 还要大的话，那当然取不了
			// 反之 r - i + 1 比 z[i - l + 1] 小，那也不能取大的
			// 因为只有 i - l + 1 到 r - l + 1 是相等的 
        }
        
        // 从 z[i] 开始尝试扩展匹配
        // 检查 sb[1 + z[i]] 和 sb[i + z[i]] 是否相等
        while (1 + z[i] <= lenb && i + z[i] <= lenb && sb[1 + z[i]] == sb[i + z[i]]) {
            z[i] ++;     // 匹配成功，LCP 长度 + 1
        }
        
        // 如果匹配后右边界超过当前最右匹配区间，则更新区间
        if (i + z[i] - 1 > r) {
            l = i;                // 新区间的左端点
            r = i + z[i] - 1;     // 新区间的右端点
        }
    }
}

// 计算 EXKMP 数组 p 
// p[i] 表示 sa 从第 i 个字符开始的后缀与 sb 的 LCP
// ***和上面的函数几乎一模一样 
void get_p() {
    // 初始化最右匹配区间 [l, r]
    // 这区间就是 sa[l..r] = sb[1..r - l + 1]
    memset(p, 0, sizeof(p));
    for (int i = 1, l = 0, r = 0; i <= lena; i++) {
    	// i 从 1 开始，长串和短串匹配 的起始位置
        // 如果 i 在当前最右匹配区间 [l, r] 内
        if (i <= r) {
            p[i] = min(z[i - l + 1], 1LL * (r - i + 1));
        }
        
        while (1 + p[i] <= lenb && i + p[i] <= lena && sb[1 + p[i]] == sa[i + p[i]]) {
            p[i] ++;  // 匹配成功，LCP长度 + 1
        }
        
        if (i + p[i] - 1 > r) {
            l = i;           // 新区间的左端点 
            r = i + p[i] - 1; // 新区间的右端点
        }
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> sa + 1 >> sb + 1;
    lena = strlen(sa + 1);
	lenb = strlen(sb + 1);
    
    get_z();
    get_p();
	
    for (int i = 1; i <= lena; i ++) {
    	cout << p[i] << " ";
    }
    cout << "\n";
    
    return 0;
}