最长公共前缀LCP

发表于 更新于 分类于 Valine： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 预处理字符串s，得到所有s任意后缀即s[i:]和s[j:]的所有最长公共前缀
class LCP {
    vector<vector<int>> dp;
public:
    LCP(const string& s) {
        dp.resize(s.size()+1, vector<int>(s.size()+1));
        for(int j=s.size()-1;j>=0;j--) {
            for(int i=j;i>=0;i--) {
                dp[i][j]=(s[i]==s[j]?dp[i+1][j+1]+1:0);
            }
        }
    }

    int operator()(int i, int j) const {
        return dp[min(i,j)][max(i,j)];
    }
};

这个算法本身本身就是动态规划，并不难，而有时这个问题会嵌套于另一个问题里，使整体变得略复杂，而如果能想到LCP问题可以用O(n^2)预处理，则复杂问题迎刃而解。

6195. 对字母串可执行的最大删除数 - 力扣（LeetCode）

一个朴素的解法是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        // 用dp[i] 表示删除s[i:]的最大操作次数
        // 删除一个长度为j的前缀之后得到的是一个子问题：s[i+j:]的最大操作次数
        // 能删除s[i:i+j]的前提是s[i:i+j]==s[i+j:i+j+j]
        vector<int> dp(n, 1);
        for(int i=n-2;i>=0;i--) {
            for(int j=1;j<=(n-i)/2;j++) {
                if(memcmp(&s[i], &s[i+j], j) == 0) { // s[i:i+j]==s[i+j:i+j+j]
                    dp[i] = max(dp[i], 1+dp[i+j]);
                }
            }
        }
        return dp[0];
    }
};

如果将memcmp(&s[i], &s[i+j], j)视为O(n)的复杂度，那么算法整体是O(n^3)复杂度。

但如果我们预处理得到s所有后缀的最长公共前缀的长度，就可以判断长度是否>=j来代替判断子串相等

从而把O(n3)的复杂度降到O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        // 用dp[i] 表示删除s[i:]的最大操作次数
        // 删除一个长度为j的前缀之后得到的是一个子问题：s[i+j:]的最大操作次数
        // 能删除s[i:i+j]的前提是s[i:i+j]==s[i+j:i+j+j]
        LCP lcp(s);
        vector<int> dp(n, 1);
        for(int i=n-2;i>=0;i--) {
            for(int j=1;j<=(n-i)/2;j++) {
                if(lcp(i, i+j)>= j) { // s[i:i+j]==s[i+j:i+j+j]
                    dp[i] = max(dp[i], 1+dp[i+j]);
                }
            }
        }
        return dp[0];
    }
};