Leetcode 1392 最长快乐前缀（技巧）

Description

「快乐前缀」是在原字符串中既是非空前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的最长快乐前缀。

如果不存在满足题意的前缀，则返回一个空字符串。

Examples input

level

Examples Output

l

思路

估计出题人也没有想到这道 hard 题被这么多人水过去了，也不知道是不是数据不够强。

那就来说说思路吧~

标准的 KMP 解法

我们知道在 KMP 里 next[i] 代表模式串第 $i$ 个元素之前最长的等值前后缀的长度。

那么，显然这道题的结果就出来了。

class Solution {
public:
    int nextval[100005];
    string longestPrefix(string s) {
        int n = s.length();
        int j = -1;
        nextval[0] = -1;
        for (int i = 0; i <= n;) {
            if (j == -1 || s[i] == s[j]) {
                nextval[++i] = ++j;
            } else
                j = nextval[j];
        }
        // for (int i = 0; i <= n; i++) {
        //     cout << nextval[i] << " ";
        // }
        // cout << endl;
        return s.substr(0, nextval[n]);
    }
};

字符串 hash 做法

字符串 hash 的方法有很多，但本质上我们要很快的求出给定串每个前缀以及每个后缀的 hash 值。

然后遍历时去比较该 hash 值是否相等，若相等则判断此时的前后缀是否等值即可（相当于处理哈希冲突）。

这里我使用了一种 $k$ 进制表示字符串的方法来计算 hash，计算的方法为：

$$ premit[i] = (premit[i – 1] + (s[i] – ‘a’) * k^i) \% mod $$

$$ lstmit[i] = (lstmit[i + 1] * k + s[i] – ‘a’) \% mod $$

其实 premit 与 lstmit 就类似于给定一个十进制数，然后计算某一段前缀以及后缀的值一样。

其中 $k$ 可随意选取，选取的好坏可能会导致不同的哈希冲突率，建议取 $26$ 以上的质数。

其中 $mod$ 也建议取一个大一点的质数。

typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int sat = 1e3 + 7;
const double eps = 1e-8;

class Solution {
public:
    LL premit[maxn];
    LL lstmit[maxn];
    LL gethash(int left, int right) {
        if (left <= 0) {
            return premit[right];
        } else {
            return lstmit[left];
        }
    }
    void init(const string &s) {
        int len = s.length();
        premit[0] = s[0] - 'a';
        for (int i = 1, sa = sat; i < len; i++, sa = LL(sa) * sat % mod) {
            premit[i] =
                (premit[i - 1] % mod + (((s[i] - 'a') * 1LL * sa) % mod)) % mod;
        }
        lstmit[len - 1] = s[len - 1] - 'a';
        for (int i = len - 2; i >= 1; i--) {
            lstmit[i] = (lstmit[i + 1] * sat % mod + s[i] - 'a') % mod;
        }
    }
    string longestPrefix(string s) {
        init(s);
        int len = s.length();
        for (int i = len - 2; i >= 0; i--) {
            if (gethash(0, i) == gethash(len - i - 1, len - 1)) {
                if (s.substr(0, i + 1) == s.substr(len - i - 1, i + 1)) {
                    return s.substr(0, i + 1);
                }
            }
        }
        return "";
    }
};

Python 无脑暴力

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        for i in range(n - 1, 0, -1):
            if s.endswith(s[:i]):
                return s[-i:]
        return ""

C++17 新特性 string_view 加持下的无脑暴力

class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        std::string_view view = s;
        for (int k = n - 1; k >= 1; k--) {
            if (view.substr(0, k) == view.substr(n - k, k))
                return s.substr(0, k);
        }
        return "";
    }
};