Z 函数（扩展 KMP）

约定：字符串下标以 0 为起点。
对于个长度为 n 的字符串 。定义函数 z[i] 表示 s 和 s[i, n - 1]（即以 s[i] 开头的后缀）的最长公共前缀（LCP）的长度。 被称为 s 的 Z 函数。特别地，z[0] = 0。
国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP。

例子

• “aaaaa” - [0,4,3,2,1]
• “aaabaab” - [0,2,1,0,2,1,0]
• “abacaba” - [0,0,1,0,3,0,1]

BF

int[] z_func(String s) {
     int n = s.length();
    int[] z = new int[n];
    for (int i = 1; i < n; i++) {
         while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
            z[i]++;
    }
    return z;
}

线性算法

核心思想：利用已经计算过的内容
对于i我们称[i, i + z[i] - 1为i的匹配段(segment matches)
z函数.pdf

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] z = z_func(s);
        System.out.println(Arrays.toString(z));
    }
    static int[] z_func(String s) {
        int n = s.length();
        int l = 0, r = 0;
        int[] z = new int[n];
        for (int i = 1; i < n; i++) {
            if (i <= r && z[i - l] < r - i + 1) {
                z[i] = z[i - l];
            } else {
                z[i] = Math.max(0, r - i + 1);
                while (i + z[i] < n && s.charAt(i + z[i]) == s.charAt(z[i]))
                    z[i]++;
            }
            if (i + z[i] - 1 > r) {
                r = i + z[i] - 1;
                l = i;
            }
        }
        return z;
    }
}

线性算法图例网站

复杂度分析

类似于马拉车算法
对于内层循环，每次执行都会使得r至少向后移动一位，而r < n - 1所以一共只会执行n次
外层循环复杂度为O(n)
故总时间复杂度为O(n)

应用

2223. 构造字符串的总得分和

裸题/模板题

你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 si 。

• 比方说，s = “abaca” ，s1 == “a” ，s2 == “ca” ，s3 == “aca” 依次类推。

si 的 得分 为 si 和 sn 的 最长公共前缀 的长度（注意 s == sn ）。
给你最终的字符串 s ，请你返回每一个_ _si 的 得分之和 。

示例 1：
输入：s = “babab” 输出：9 解释： s1 == “b” ，最长公共前缀是 “b” ，得分为 1 。 s2 == “ab” ，没有公共前缀，得分为 0 。 s3 == “bab” ，最长公共前缀为 “bab” ，得分为 3 。 s4 == “abab” ，没有公共前缀，得分为 0 。 s5 == “babab” ，最长公共前缀为 “babab” ，得分为 5 。 得分和为 1 + 0 + 3 + 0 + 5 = 9 ，所以我们返回 9 。
示例 2 ：
输入：s = “azbazbzaz” 输出：14 解释： s2 == “az” ，最长公共前缀为 “az” ，得分为 2 。 s6 == “azbzaz” ，最长公共前缀为 “azb” ，得分为 3 。 s9 == “azbazbzaz” ，最长公共前缀为 “azbazbzaz” ，得分为 9 。 其他 si 得分均为 0 。 得分和为 2 + 3 + 9 = 14 ，所以我们返回 14 。

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母。

class Solution {
    public long sumScores(String s) {
        int[] z = z_func(s);
        long res = s.length();
        for (int x : z)
            res += x;
        return res;
    }
    int[] z_func(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r && z[i - l] < r - i + 1)
                z[i] = z[i - l];
            else {
                z[i] = Math.max(0, r - i + 1);
                while (i + z[i] < n && s.charAt(i + z[i]) == s.charAt(z[i]))
                    z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}

28. 实现 strStr()

字符串匹配
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf()) 定义相符。

示例 1：
输入：haystack = “hello”, needle = “ll” 输出：2
示例 2：
输入：haystack = “aaaaa”, needle = “bba” 输出：-1
示例 3：
输入：haystack = “”, needle = “” 输出：0

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

class Solution {
    public int strStr(String t, String p) {
        int n = t.length(), m = p.length();
        p = p + "#" + t;
        int[] z = z_func(p);
        for (int i = m + 1; i <= m + n; i++) {
            if (z[i] == m)
                return i - 1 - m;
        }
        return -1;
    }
    int[] z_func(String s) {
        int n = s.length();
        int l = 0, r = 0;
        int[] z = new int[n];
        for (int i = 1; i < n; i++) {
            if (i <= r && z[i - l] < r - i + 1)
                z[i] = z[i - l];
            else {
                z[i] = Math.max(0, r - i + 1);
                while (i + z[i] < n && s.charAt(i + z[i]) == s.charAt(z[i]))
                    z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}