数据结构与算法笔记 | 字符串

7月 7 2018 数据结构与算法 13 分钟读完 (约 1998 字)

算法题中经常会遇到字符串处理题，可易可难。

子串和子序列问题

辨析：子串和子序列的区别？
一般说来，串要求是必须是紧挨着的，而序列允许跳跃，只要保持顺序就可以。下面来看两类经典的子串和子序列处理问题

1. 最长回文子串和最长回文子序列

1.1 最长回文子串长度

当一个字符串和他的逆序串完全相等时，我们称这是一个回文串(Palindrome)，如 “malayalam”, “dad”, “appa”等。
输入一个字符串，输出其最长回文子串的长度
来源：POJ 3974，SPOJ-IPS

奇数串与偶数串的处理：
如果采取的是逆序之后和原子串比较的办法, 对于奇数子串和偶数子串可以统一处理，但由于回文的位置不定，需要遍历所有字符串所有位置一一进行逆序，复杂度比较高。故一般思路应是从中间往两边扩散的方法来进行判定. 注意从中间开始往两边扩散的方法判定时奇数串和偶数串的判定标准是不一样的. 比如对于一个奇数回文串 madam, 除去中间的 d 字符, 剩下的两两匹配. 对于一个偶数回文串, 如 elle, 都是两两匹配的. 处理奇串和偶串总结大致有以下三种方法：

第一种办法最直接，就是将奇数串与偶数串使用两段语句，分开来处理。

第二种办法是加入特殊字符进行填充，将奇数串和偶数串都转化为奇数串。

public int getPalindromeLength(String str) {
    // 加入特殊符号 '#'
    StringBuilder builder = new StringBuilder();
    builder.append('#');
    for(char c : str) {
        builder.append(c);
        builder.append('#');
    }
    // 统一处理
    ......
}

第三种办法利用到了一个特性，也就是偶数串最中间的两个字母一定是相同的，所以我们在循环的过程中判断相邻两个字符串是否相等，来统一识别出奇数串和偶数串。

1
2
3

for (int i = 0, l, r; i < str_len; ++i) {    // 循环数组
    for (l=i; s[i]==s[i+1];) ++i;   // 定位 i 的位置，r初始便可设置为i+1
}

第三种方法的判断方式最为简洁，但是复杂度没有变化，仍然属于 $O(n^2)$ 级别

选择好中心后，需要两个指针分别向左和向右扩散。扩散方式也有两种，一种是+1扩散，另一种是曼彻斯特算法，将在下一部分介绍，这里的解一就采用+1扩散的方式。

解：

#include <bits/stdc++.h>
using namespace std;

int longestPalindrome(string);

int main() {
    string s = "cbbca";
    int ans = longestPalindrome(s);
    printf("longest length of Palindrome %s is %d\n", s.c_str(), ans);
    return 0;
}

int longestPalindrome(string s) {
    int longest = -1;
    for(int i = 0, l, r; i < s.size(); ++i) {
        for(l = i; i+1<s.size() && s[i]==s[i+1]; ++i);
        for(r = i; l>=0 && r<s.size() && s[l]==s[r]; --l, ++r); // +1 扩散 
        int palindrome  = r-l-1;
        longest = longest > palindrome ? longest : palindrome;
    }
    return longest;
}

1.2 寻找最大子串

从中间向两边扩散:
一种方法是从中间开始向两边扩展，见解一中的代码

1 2	for(r = i; l>=0 && r<s.size() && s[l]==s[r]; --l, ++r); // l+1为回文子串位置，r-l-1即为回文子串长度

另一种办法叫做Manchester算法，这个算法在+1拓展的方法基础上加入了动态规划的思想，充分利用先前计算得到的结果进行合理跳步。具体阐述为：

初始化回文子串达到的右边界right = -1，该回文串中心id=-1，
遍历字符串，起始遍历位置 i = 0，回文串半径 r = 1
遍历过程中，如果 i 在 id 和 right 之间，以i为中心的最大子串半径 rad[i] >= min(rad[2*id-i], right-i)（因为如果 rad[2*id-i]<right-i ，则i和它对称点环境一样都在right内部，所以其半径相等，为 rad[2*id-i]；否则若 rad[2*id-i]>right-i，则说明对称点突破了right内部环境，所以点 i 为中心的半径至少业为right-i ）；如果i在right右边则无法判断，只能暂时初始化为1，然后+1扩散进行判断。
当新的右边界i+r-1突破原有右边界right后，就可以将 i 作为新的最靠右的回文子串中心，即 right=i+r-1; id=i;
更新 rad[i] = r
遍历结束，得到以每个字符为中心的最长回文半径数组，数组中最大值即为所求最长回文子串长度。

Manchester

由描述可知，该算法需要通过添加特殊字符的方式统一处理奇偶串，我们采用Manchester算法处理问题1.2

解：LeetCode链接：

int[] rad = new int[str.length];   // rad[i] 表示以第i个字符为中心的回文子串半径
int right = -1; // right表示遍历过程中回文子串所到达的右边界
int id = -1;    // 遍历过程中到达最远边界（right）的回文子串中心
for(int i = 0; i < str.length; ++i) {
    int r = 1;  // 半径初始化为最小值1
    if(i <= right) {    // 若此时遍历位置i小于之前遍历曾到达的最远边界，则可以借一波之前的成果
        r = Math.min(rad[id]-i+id, rad[2*id-i]);    // 半径起码为的最小值
    }
    while(i-r >= 0 && i+r <= str.length && str[i-r]==str[i+r]) {
        ++r;
    }
    if(i+r-1 > right) {
        right = i+r-1;
        id = i;
    }
    rad[i] = r;
}

1.3 最长回文子序列长度

子序列问题一般都会涉及到动态规划，动态规划表达式的构建是难点，好处是不用考虑奇偶串的统一的处理情况了。我们考虑构建二维dp数组，其中 dp[l][r] 表示左边界为l，右边界为r的最长回文子序列个数，则 dp[0][len-1] 即为所求。
接下来分类讨论得到 dp[l][r] 的递推式，初始情况为 l==r，此时dp[l][r]=1，此时可以将 l-- 和 r++，若 str[l-1]==str[r+1]，则可以继续推进，即dp[l-1][r+1] = dp[l][r]+2;
否则若 str[l]!=str[r]，则等价于从[l-1,r] 和 [l,r+1] 范围内选出最大值，即 dp[l-1][r+1] = max(dp[l-1][r], dp[l][r+1])。
令 l = l-1, r = r+1，得到 dp[l][r] 的递推公式：

1 2	if(str[l] == str[r]) dp[l][r] = dp[l+1][r-1] + 2 else dp[l][r] = max(dp[l][r-1], dp[l+1][r])

遍历顺序应注意l是从大往小遍历，r是从小往大遍历。

解：LeetCode 516

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();
        if(len <= 0) return len;
        int dp[len][len];
        for(int i = 0; i < len; ++i) {
            memset(dp[i], 0, len*sizeof(int));
        }
        for(int l = s.size()-1; l >= 0; --l) {
            dp[l][l] = 1;
            for(int r = l+1; r < s.size(); ++r) {
                if(s[l] == s[r]) {
                    dp[l][r] = dp[l+1][r-1] + 2;
                } else {
                    dp[l][r] = std::max(dp[l][r-1], dp[l+1][r]);
                }
            }
        }
        return dp[0][len-1];
    }
};

2. 最长公共子序列（Longest Common Sequence）和最长公共子串（Longest Common Substring）

两个都可简称为LCS，最长公共子串和最长公共子序列都可以用动态规划解决。所不同的是，当串 s1[i]≠s2[j],i>0,j>0 时，公共子串的 dp[i][j]=0 而公共子序列的 dp[i][j]=max{dp[i-1][j],dp[i][j-1]}，最长公共子串需要用一个额外String变量存储，而最长公共子序列就是 dp[s1.len-1][s2.len-1]。下面是两个问题的动态规划算法实现

最长公共子序列

/**
    * longest common subsequence
    * @param s1 string字符串 the string
    * @param s2 string字符串 the string
    * @return string字符串
    */
public String LCS (String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    ArrayList<ArrayList<String>> dp = new ArrayList<>(s1.length);
    for(int i=0; i<s1.length; ++i) {
        ArrayList<String> row = new ArrayList<String>(s2.length);
        for(int j=0; j<s2.length; ++j) {
            String cs = null;
            if(i==0 && j==0) {
                if(s1[i] == s2[j]) {
                    cs = String.valueOf(s1[i]);
                } else {
                    cs = "";
                }
                row.add(j, cs);
            } else if(i==0) {
                if(s1[i] == s2[j]) {
                    cs = String.valueOf(s1[i]);
                } else {
                    cs = row.get(j-1);
                }
                row.add(j, cs);
            } else if(j==0) {
                if(s1[i] == s2[j]) {
                    cs = String.valueOf(s1[i]);
                } else {
                    cs = dp.get(i-1).get(j);
                }
                row.add(j, cs);
            } else { // i!=0,j!=0
                if(s1[i] == s2[j]) {
                    cs = dp.get(i-1).get(j-1) + s1[i];
                } else if(dp.get(i-1).get(j).length() > row.get(j-1).length()){
                    cs = dp.get(i-1).get(j);
                } else {
                    cs = row.get(j-1);
                }
                row.add(j, cs);
            }
        }
        dp.add(i, row);
    }
    String lcs = dp.get(s1.length-1).get(s2.length-1);
    if(lcs.length() == 0) return "-1";
    return lcs;
}

最长公共子串

/**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        String lcs = "";
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        ArrayList<ArrayList<String>> dp = new ArrayList<>(s1.length);
        for(int i=0; i<s1.length; ++i) {
            ArrayList<String> row = new ArrayList<String>(s2.length);
            for(int j=0; j<s2.length; ++j) {
                String cs = null;
                if(i==0 || j==0) {
                    if(s1[i] == s2[j]) {
                        cs = String.valueOf(s1[i]);
                        if(cs.length() > lcs.length()) {
                            lcs = cs;
                        }
                    } else {
                        cs = "";
                    }
                    row.add(j, cs);
                } else { // i!=0,j!=0
                    if(s1[i] == s2[j]) {
                        cs = dp.get(i-1).get(j-1) + s1[i];
                        if(cs.length() > lcs.length()) {
                            lcs = cs;
                        }
                    } else {
                        cs = "";
                    }
                    row.add(j, cs);
                }
            }
            dp.add(i, row);
        }
        return lcs;
    }

大整数运算

大整数运算方便Java具有优势，因为Java自带大整数处理的BigInteger类；而C/C++需要手动构建字符串，模拟手工运算来实现大整数的加减乘除。

#算法 #数据结构 #串