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.

---

给定一个字符串，要求找出这个字符串中前缀和后缀相等的最长子串。本质是KMP算法中求解模式串的next数组的过程。KMP算法解读请看这篇博客： http://code.bitjoy.net/2016/05/05/leetcode-implement-strstr/

因为在KMP算法中，next[i]表示i之前的字符串中前缀和后缀相等的最大长度，不包括i，而本题是需要考虑以最后一个字符结尾的情况，所以我们在原字符串后面随便增加一个char，则可直接套用KMP中求解next数组的方法，然后取next[n-1]即可。

完整代码如下：

class Solution {
public:
	string longestPrefix(string s) {
		s = s + ".";
		int n = s.size();
		vector<int> next(n, 0);
		next[0] = -1;
		int i = 0, j = -1;
		while (i < n - 1) {
			if (j == -1 || s[i] == s[j]) {
				++i;
				++j;
				next[i] = j;
			}
			else {
				j = next[j];
			}
		}
		return s.substr(0, next[n - 1]);
	}
};

本代码提交AC，用时60MS。