【华为OD机试|01】最远足迹（Java/C/Py/JS）

题目描述：

给定一个字符串t，表示一个足迹的时间序列（字符串只包含小写字母'a' - 'z'），请找到最远的两个不重叠的重复子串的长度。

解题思路：

这是一个字符串匹配问题，可以通过后缀自动机（Suffix Automaton）或者Hash来解决。这里提供一个简单的后缀自动机解法。

后缀自动机构建后，我们可以考虑每个状态代表的子串，并寻找其最长的可以通过添加一个字符扩展到另一个状态的后缀。这两个状态的最长长度就是不重叠的重复子串的长度。

以下是Java的示例代码：

public class Solution {
    public int getMaxRepeatSubstr(String t) {
        int n = t.length();
        int[][] suffix = new int[n][26];
        int[] parent = new int[n];
        int[] len = new int[n];
        int j = 0, p = 0;
        for (int i = 0; i < n; ++i) {
            j = (j + 1) % n;
            parent[j] = p;
            len[j] = len[p] + 1;
            p = j;
            char c = t.charAt(i);
            while (p != 0 && suffix[p][c - 'a'] == 0) {
                suffix[p][c - 'a'] = j;
                p = parent[p];
            }
            if (p != 0) {
                int k = suffix[p][c - 'a'];
                if (len[j] - len[k] > 1) {
                    return len[j] - len[k] - 1;
                }
                p = k;
            }
        }
        return 0;
    }
}

在这个代码中，suffix[i][j]表示以字符'a' + j为结尾的长度为i的字符串的后缀开始位置，parent[i]表示状态i的父状态，len[i]表示状态i代表的后缀的长度。通过维护这个后缀自动机，我们可以在线性时间复杂度内找到答案。