> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/1392.-longest-happy-prefix.md).

# 1392. Longest Happy Prefix

https\://leetcode.com/problems/longest-happy-prefix/

A string is called a *happy prefix* if is a **non-empty** prefix which is also a suffix (excluding itself).

Given a string `s`. Return the **longest happy prefix** of `s` .

Return an empty string if no such prefix exists.

**Example 1:**

```
Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
```

**Example 2:**

```
Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
```

**Example 3:**

```
Input: s = "leetcodeleet"
Output: "leet"
```

**Example 4:**

```
Input: s = "a"
Output: ""
```

**Constraints:**

* `1 <= s.length <= 10^5`
* `s` contains only lowercase English letters.

对给定str找最长匹配的前后缀，前后缀之间可以有重叠。前后缀匹配=> KMP。KMP本质可看作是dp，dp\[i]存以pattern字符串A中以i为底可匹配的最长前后缀长度。ptr初始为dp\[i -1]，当A\[i]和dp\[ptr]不等时，ptr = dp\[ptr]，直到相等或ptr == 0。比如aacaad的dp = \[0,1,0,1,2,0]，匹配d时先检查d和c是否相等，对应aac和aad；不等时往前跳到下一个与A\[i-1]匹配的位置，匹配a和d，对应aa和ad。过程如下，方块为未知i，△为prefix中下一个和A\[i]匹配的字符：

![](http://127.0.0.1:57243/paste-25500b656595a0a72f08dd99bf312cb2941a1536.jpg)

除此之外还可以用rolling hash做，只用O(1)空间，参加lee215的[答案](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/longest-happy-prefix/discuss/547237/JavaPython-Rolling-Hash)。

```python
class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        dp = [0] * n
        for i in range(1, n):
            j = dp[i - 1]
            while j > 0 and s[i] != s[j]:
                j = dp[j - 1]
            if s[i] == s[j]:
                dp[i] = j + 1
        return s[:dp[n - 1]]
        
```