python3 解法, 执行用时: 1819 ms, 内存消耗: 29.2 MB, 提交时间: 2024-10-19 14:14:05

class Solution:
    def calc_z(self, s: str) -> list[int]:
        n = len(s)
        z = [0] * n
        box_l = box_r = 0  # z-box 左右边界
        for i in range(1, n):
            if i <= box_r:
                z[i] = min(z[i - box_l], box_r - i + 1)  # 改成手动 if 可以加快速度
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                box_l, box_r = i, i + z[i]
                z[i] += 1
        return z

    def minStartingIndex(self, s: str, pattern: str) -> int:
        pre_z = self.calc_z(pattern + s)
        suf_z = self.calc_z(pattern[::-1] + s[::-1])
        suf_z.reverse()  # 也可以不反转，下面写 suf_z[-i]
        m = len(pattern)
        for i in range(m, len(s) + 1):
            if pre_z[i] + suf_z[i - 1] >= m - 1:
                return i - m
        return -1

java 解法, 执行用时: 54 ms, 内存消耗: 46.6 MB, 提交时间: 2024-10-19 14:13:51

class Solution {
    public int minStartingIndex(String s, String pattern) {
        int[] preZ = calcZ(pattern + s);
        int[] sufZ = calcZ(rev(pattern) + rev(s));
        // 可以不反转 sufZ，下面写 sufZ[sufZ.length - i]
        int n = s.length();
        int m = pattern.length();
        for (int i = m; i <= n; i++) {
            if (preZ[i] + sufZ[sufZ.length - i] >= m - 1) {
                return i - m;
            }
        }
        return -1;
    }

    private int[] calcZ(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] z = new int[n];
        int boxL = 0;
        int boxR = 0; // z-box 左右边界
        for (int i = 1; i < n; i++) {
            if (i <= boxR) {
                z[i] = Math.min(z[i - boxL], boxR - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                boxL = i;
                boxR = i + z[i];
                z[i]++;
            }
        }
        return z;
    }

    private String rev(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

cpp 解法, 执行用时: 95 ms, 内存消耗: 71.7 MB, 提交时间: 2024-10-19 14:13:37

class Solution {
    vector<int> calc_z(string s) {
        int n = s.length();
        vector<int> z(n);
        int box_l = 0, box_r = 0; // z-box 左右边界
        for (int i = 1; i < n; i++) {
            if (i <= box_r) {
                z[i] = min(z[i - box_l], box_r - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                box_l = i;
                box_r = i + z[i];
                z[i]++;
            }
        }
        return z;
    }

public:
    int minStartingIndex(string s, string pattern) {
        vector<int> pre_z = calc_z(pattern + s);
        ranges::reverse(pattern);
        ranges::reverse(s);
        vector<int> suf_z = calc_z(pattern + s);
        ranges::reverse(suf_z); // 也可以不反转，下面写 suf_z[suf_z.size() - i]
        int m = pattern.length();
        for (int i = m; i <= s.length(); i++) {
            if (pre_z[i] + suf_z[i - 1] >= m - 1) {
                return i - m;
            }
        }
        return -1;
    }
};

golang 解法, 执行用时: 38 ms, 内存消耗: 10.5 MB, 提交时间: 2024-10-19 14:13:24

func calcZ(s string) []int {
    n := len(s)
    z := make([]int, n)
    boxL, boxR := 0, 0 // z-box 左右边界
    for i := 1; i < n; i++ {
        if i <= boxR {
            z[i] = min(z[i-boxL], boxR-i+1)
        }
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            boxL, boxR = i, i+z[i]
            z[i]++
        }
    }
    return z
}

func rev(s string) string {
    t := []byte(s)
    slices.Reverse(t)
    return string(t)
}

func minStartingIndex(s, pattern string) int {
    preZ := calcZ(pattern + s)
    sufZ := calcZ(rev(pattern) + rev(s))
    slices.Reverse(sufZ) // 也可以不反转，下面写 sufZ[len(sufZ)-i]
    m := len(pattern)
    for i := m; i <= len(s); i++ {
        if preZ[i]+sufZ[i-1] >= m-1 {
            return i - m
        }
    }
    return -1
}