LeetCode刷题【1392】最长快乐前缀

输入：s = "level"
输出："l"
解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。

输入：s = "ababab"
输出："abab"
解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

KMP模式串预处理方法
其实就是KMP算法中模式串（Pattern）的预处理算法

整个过程也可以当做是一个动态规划的算法过程来理解，其本质是状态机，额，这块就涉及知识盲区了，大学的知识早就忘记了。

还是回到动态规划的话题来说吧，比较好理解点

借用一个案例模式串来讲解下

A B A C D A B A B C

我们需要定义的DP数组的含义是，从下标0开始到当前字符结束的子串中，最长的前缀和结尾相同的子串的结束下标，感觉非常绕不像人话。

以上面的子串A B A C D A B A为例，我们解释一下，这部分内容的 前缀和结尾相同的最长部分为A B A

他在头部的结束下标为 2 ,对应为第二个A 字符所以对应的这部分为dp[7] = 2，或者简单理解为该子串的长度-1

对于前面没有匹配的部分，我们用-1来表示，这样我们可以直接先目测得到上面案例字符串算出来的dp[]数组为

 A   B   A   C   D   A   B   A   B   C
-1  -1   0  -1  -1   0   1   2   1  -1

根据上面的结果我们可以看到，dp[i]的值依赖于 pattern[i] 与 pattern[dp[i-1]+1]的匹配情况

如果能匹配则dp[i] = dp[i-1] + 1

不能匹配的话则继续与pattern[dp[dp[i-1]]+1]匹配，不能的话则继续再往前查找

照旧拿上面的案例举个栗子

                     A   B   A   C   D   A   B   A   B
                    -1  -1   0  -1

 A   B   A   C   D   A   B   A   B
                     0   1   2   ↑

箭头部分的B与前缀的C未能匹配，所以继续前移，找到前面的字符A的dp[7] = 2的值作为下标的时候dp[2] = 0的情况下，如下

                             A   B   A   C   D   A   B   A   B
                            -1  -1   0  -1

 A   B   A   C   D   A   B   A   B
                     0   1   2   ↑

发现能匹配完成，则最终得到对应的dp[8] = dp[2] + 1 = 1

最终我们可以知道数组末尾的值就是题目要求的最长快乐前缀的结束字符下标，在KMP中一般用next[]数组表示，而不是写成dp[]数组

代码

class Solution {
    public String longestPrefix(String s) {
        int[] next = getNextArr(s.toCharArray());
        int last = next[next.length - 1];
        if (last == -1) return "";
        return s.substring(0, last + 1);
    }
    private int[] getNextArr(char[] arr) {
        int[] next = new int[arr.length];
        Arrays.fill(next, -1);
        int idx = 0;
        int p = -1;
        while (++idx < arr.length){
            while ( p != -1 && arr[p+1] != arr[idx]){
                p = next[p];
            }
            if (arr[p+1] == arr[idx]){
                p++;
            }
            next[idx] = p;
        }
        return next;
    }
}