难度: Hard
「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。如果不存在满足题意的前缀，则返回一个空字符串 "" 。
示例 1：
输入：s = "level" 输出："l" 解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。
示例 2：
输入：s = "ababab" 输出："abab" 解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
提示：
1 <= s.length <= 105s 只含有小写英文字母运行时间: 147 ms
内存: 20.2 MB
class Solution:
def longestPrefix(self, s: str) -> str:
nxt=[0]
i=1
pos=0
while i<len(s):
if s[pos]==s[i]:
i+=1
pos+=1
nxt.append(pos)
elif pos:
pos=nxt[pos-1]
else:
i+=1
nxt.append(0)
return s[:nxt[-1]]
题解采用了KMP算法中的部分思路，构建了一个部分匹配表，用于确定字符串中的最长快乐前缀。算法首先初始化一个长度为s的列表nxt，其中nxt[i]表示字符串s的前i个字符中，最长的相同前缀和后缀的长度。迭代过程中，通过比较当前字符和位置pos指向的字符，如果相同，则更新nxt数组，并将i和pos同时右移。如果不相同，则将pos更新到nxt数组的前一个位置，继续比较，直到找到匹配或遍历完成。最后，nxt数组的最后一个元素即为最长快乐前缀的长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestPrefix(self, s: str) -> str:
nxt = [0] # 初始化部分匹配表，nxt[0]为0
i = 1 # 从第二个字符开始
pos = 0 # 初始化匹配位置
while i < len(s): # 遍历字符串
if s[pos] == s[i]: # 当前字符与匹配位置字符相同
i += 1
pos += 1
nxt.append(pos) # 更新nxt数组
elif pos:
pos = nxt[pos - 1] # 字符不匹配，回溯到前一个匹配位置
else:
i += 1
nxt.append(0) # 没有匹配的情况
return s[:nxt[-1]] # 返回最长快乐前缀
在KMP算法中，部分匹配表`nxt`的作用是在发生不匹配事件时，提供一个跳过不必要比较的机制。当当前字符不匹配时，`nxt[pos - 1]`表示前一个位置的最长前缀和后缀匹配的长度，这代表了可以安全跳过的字符数。这样的跳转避免了从头开始的重复比较，显著提升了匹配效率。通过回溯到`nxt[pos - 1]`，算法尝试在不匹配的位置找到之前已经匹配成功部分的下一个可能匹配点，从而继续进行后续的比较而不是完全重置。
初始化`nxt = [0]`是因为`nxt[0]`代表着字符串的第一个字符的前缀和后缀的最大匹配长度。由于单个字符没有前缀或后缀，因此其最长相同前后缀的长度为0。这是定义上的必然结果，因为不存在可以匹配的前缀或后缀。如果`nxt[0]`值为1或其他值，则会错误地表示存在非实际的匹配，影响算法的正确性和逻辑。
算法通过维护整个字符串的部分匹配表`nxt`确保这一点。`nxt`数组中的最后一个元素`nxt[-1]`存储的是整个字符串中最长的相同前缀和后缀的长度。即使存在多个相同长度的最长前缀和后缀，`nxt[-1]`总是代表了整个字符串中最长的一个。由于算法只返回`s[:nxt[-1]]`，它自然只返回这个最长的快乐前缀。
是的，这种说法依然成立。在KMP算法和其变种的实现中，每个字符在构建部分匹配表`nxt`的过程中确实最多被比较一次。即使在极端情况下，例如字符串由相同字符组成，算法中的回溯机制（通过`nxt`数组）确保字符比较不会重复进行，而是跳过已经比较过的部分。这保证了算法的高效性，即使在所有字符相同的情况下。