题目描述

"快乐前缀"是在原字符串中既是前缀又是后缀（不包括整个字符串本身）的最长字符串。给定一个字符串 s，返回其最长快乐前缀。如果不存在则返回空字符串。本题本质是求 KMP 算法中的最长公共前后缀（LPS/next 数组），利用部分匹配表的思想可以在 O(n) 时间内求解。