# 1392. 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]]
        
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/1392.-longest-happy-prefix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.