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^5scontains only lowercase English letters.
Solution: Rolling Hash
Time complexity: O(n) / worst case: O(n^2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: string longestPrefix(string_view s) { const int kMod = 16769023; const int kBase = 128; const int n = s.length(); int p = 0; int q = 0; int a = 1; int ans = 0; for (int i = 1; i < n; ++i) { p = (p + a * s[i - 1]) % kMod; q = (q * kBase + s[n - i]) % kMod; a = (a * kBase) % kMod; if (p == q && s.substr(0, i) == s.substr(n - i)) ans = i; } return string(s.substr(0, ans)); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment