leetcode 1392

问题

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:

1
2
3
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:

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

Example 3:

1
2
Input: s = "leetcodeleet"
Output: "leet"

Example 4:

1
2
Input: s = "a"
Output: ""

Constraints:

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

分析

思路1: 采用KMP算法求最长公共前后缀中的部分代码来进行求解。prefixTable[]。

思路2: 使用字符串hash，取一固定制P（一般取P = 131 或者 P=1331），把字符串看作P进制数，并分配一个大于0的数值，代表每种字符。一般来说，我们分配的数值都远小于P。例如对于小写字符构成的字符串，可以令 a = 1，b=2，.. z = 26。取一固定制M，求出该P进制数对M的余数，作为该字符串的Hash值。通常我们选取 $ M = 2^{64}$ ，即直接使用 unsigned long long 类型存储这个Hash值，在计算时不处理算数的益出问题，产生溢出相当于自动对 $2^{64}$ 取模，这样可以避免低效的取模运算。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// KMP: prefixTable
class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        if (n == 1) 
            return "";
        vector<int> prefixTable(n, 0);
        int len = 0;
        int i = 1;
        while ( i < n ) {
            if (s[i] == s[len]) {
                prefixTable[i++] = ++len;
            } else {
                if (len == 0) {
                    prefixTable[i++] = 0;
                } else {
                    len = prefixTable[len-1];
                }
            }
        }
        return s.substr(0, prefixTable[n-1]);
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 字符串Hash
// leetcode中把溢出看作是异常来进行处理，所以需要mod上一个大的素数 10e9 + 7
// 一般情况下使用unsigned long long 使其自然溢出即可
class Solution {
public:
    const int P = 131;
    const int mod = 1000000007;
    string longestPrefix(string s) {
        unsigned long long prefixHash = 0, suffixHash = 0;
        int n = s.size(), ans = 0;
        int i = 0, j = n-1;
        unsigned long long tmp = 1;
        while (i < n-1) {
            tmp = (i == 0? 1: (tmp*P)%mod);
            suffixHash = ((s[j]-'a'+1)*tmp + suffixHash)%mod;
            prefixHash = (prefixHash*P + s[i] - 'a' + 1)%mod;
            if (suffixHash == prefixHash) {
                ans = max(ans, i+1);
            }
            ++i;
            --j;
        }
        return s.substr(0, ans);
    }
};