字符串

Posted on | Post modified: | In |
Words count in article: 1.3k

14. 最长公共前缀

  • 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

方法一：纵向扫描，从每个字符串的第0号位置开始，依次向后扫描，每次扫描所有字符串的该位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//C++ O(n*m)
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty())
            return "";
        int n = strs.size(), m = strs[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++){
                if(strs[j].size() < i || strs[j][i] != strs[0][i])
                    return strs[0].substr(0,i);
            }
        return strs[0];
    }
};

回文串

最长回文子串

  • 给定一个字符串 s，找到 s 中最长的回文子串。
  1. manacher算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    manacher算法，思想与KMP很像，kmp在子串匹配的过程中，利用子串已有的信息，加快子串的滑动，减少不必要的计算。
        而manacher在对以每个i为中心的回文串遍历时，利用前面已经求出的回文串来减少计算。每个中心i可以看作我们计算的小单元。
        而它们之间有个很重要的特性就是对称。
        举例说明：
            在一个以mid为中心r[mid]为半径大回文串中，要求以右边某个点j为中心的回文串，可以利用关于mid对称点i，
        根据i的回文串大小r[i]，可以推测j的回文大小。
        当j不在mid的回文串中时，直接用朴素的中心扩散就行。
        当j在mid的回文串中时，需要分情况讨论：
            1. 第一个显然的情况是：i的回文串依然在mid回文串的范围内，即 i - r[i] > mid - r[mid]。这时j的回文串半径一定等于r[i]。
        为了方便计算，保存右边界位置R，再利用对称性，得到条件 r[i] < R - j
            2. 当i的回文左边界刚好与mid左边界相等时，不能确定j的大小，但可以保证r[j] >= r[i]。
            3. 当i的回文左边界超出了mid左边界时， r[j]一定等于 R - j 。因为当r[j] > R - j 时，说明j的回文右边界超出了mid右边界，
        而j和i是对称的，此时mid的边界是一定能跟着j的扩大而扩大的，而mid在j前面，已经用中心扩散求过了，所以j的右边界已不能扩散。
        
        综上，r[j] 可以取min( r[i], R - j )，再用中心扩散试探能否扩张。
        最后再维护R和mid，使得当前mid的R最远。
        
        由于manacher算法是以某个点为中心去计算其回文串，因此偶数情况下不方便使用，所以用填充字符使它变为奇数。
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int main(){
    
    while(cin >> s , s != "END"){
        int n = s.size();
        cnt ++;
        // 因为处理奇偶问题比较麻烦，因此选择填充#来将其变为奇数
        string str = "#";
        for (int i = 0 ; i < n; i ++){
            str += s[i];
            str += "#";
        }
       
        n = 2 * n + 1;
        int r[n];  // 作用同kmp的next数组，r[i]保存i位置上的最长回文串半径
        
        memset(r, 0, sizeof r);
        
        int R = 0, mid = 0;
        int max_len = 1;
        
        for (int i = 0; i < n; i ++ ){
            
            if (i < R) {
                int symmetry_i = 2 * mid - i;       // i在回文串内时利用前面已求得对称性来快速确定基准回文长度。i + sym_i = 2 * mid
                r[i] = min(R - i, r[symmetry_i]);   // 在已知是回文串的范围内，用mid左边对称点记录的r[sym_i]可节省时间
            }
            
            // 尝试扩大r[i] ，中心扩散
            int left = i - (r[i] + 1), right = i + (r[i] + 1);
            while ( left >= 0 && right < n && str[left] == str[right]){
                r[i] ++ ;
                left -- ;
                right ++;
            }
            
            if (i + r[i] > R ) R = i + r[i], mid = i;  // 维护使得当前R最远
            
            if (r[i] > max_len){
                max_len = r[i];
            }
            if ( i == r[i]) temp = i;
        }
        
        cout << max_len << endl;
       
        
    }
}

最短回文串

  • 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。、
  1. manacher
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
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    
    string shortestPalindrome(string s) {
        string str("*");
        for (const auto &c : s){
            str += c;
            str += "*";
        }
        int n = s.size();
        int r[n+1], R = 0, mid = 0, max_prefix = 0;
        memset(r, 0, sizeof r);

        for (int i = 0; i <= n; ++ i){
            if (i < R){
                int sym_i = 2 * mid - i;
                r[i] = min(R - i, r[sym_i]);
            }

            // 中心扩散
            int left = i - (r[i] + 1), right = i + (r[i] + 1);
            while (left >= 0 && right <= 2 * n && str[left] == str[right]){
                -- left, ++ right, ++ r[i];
            }

            if ( i + r[i] > R) R = i + r[i], mid = i;

            if (i == r[i]) max_prefix = i;
        }
        string rev(s);
        rev = rev.substr(max_prefix, n - max_prefix);
        reverse(rev.begin(), rev.end());
        return rev + s;
    }
};
  1. KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    
    string shortestPalindrome(string s) {
        string r(s);
        reverse(r.begin(), r.end());
        string target = ' ' + s + '*' + r;
        const int n = target.size();
        int next[n + 1];
        memset(next, 0, sizeof next);
        for (int i = 2, j = 0; i < n; ++ i){
            while (j && target[i] != target[j + 1]) j = next[j];
            if (target[i] == target[j + 1]) ++ j;
            next[i] = j;
        }
        
    return r.substr(0, r.size() - next[n - 1]) + s;
    }
};