动态规划与最长重复子串

Posted on Views:

最长重复子串问题

假设我们有一个字符串，要如何求出在这个字符串里最长的重复子串呢？比如给出字符串abcdeefabcd，显然这个字符串的重复子串有很多，比如a、b、ab、abc 等等，那么通过观察，我们可以知道这个字符串的最长重复子串(Longest Repeated Substring)为abcd。

如果要用编程的方法来找出这个最长重复子串，应该怎么做呢？

暴力遍历

非常正常的想法是遍历，利用三重循环，每一次比较两个相等长度的子字符串是否相等，将记录下的最大长度与该子字符串进行比较，如果更长，则更新答案。简单的代码如下：

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
#include<iostream>
#include<string.h>
using namespace std;
string naiveLRS(string s)
{
    int maxm=0; //重复子字符串的最大长度
    string ans = "";
    for(int i=0;i<s.length();i++)
    {
        for(int j=i;j<s.length();j++)
        {
            string x=s.substr(i,j-i+1);  //一个子字符串
            for(int k=i+1;k<s.length();k++) //从i+1开始，因为如果从i开始，两字符串的起点相同，得到的答案必定为原字符串s
            {
                string y=s.substr(k,j-i+1); //另一个与x不相等的子字符串
                if(x == y && x.length() > maxm) //如果这两个字符串相等，并且长度比之前记录的maxm更大，则更新答案
                {
                    maxm = x.length();
                    ans = x;
                }
            }
        }
    }
    return ans;
}

int main()
{
    string s,ans;
    cout << "Enter the input string:-\n";
    cin >> s;   //输入字符串
    ans = naiveLRS(s);
    cout << "The longest repeating substring is:- " << ans << '\n'; //输出答案
    return 0;
}

显然，这种方法的时间复杂度是\(O(n^3)\)，空间复杂度为\(O(1)\)。值得一提的是，在第三层循环中，是不需要考虑如果长度\(j-i+1\)超出字符串长度的情况，因为在substr()函数中，如果给出的长度超出了字符串原本的长度，会自动截取到字符串的结尾。

动态规划

显然，前面提到的暴力解法涉及到了非常多的重复计算。而动态规划的思想，实际上就是利用“记忆”下来的数据，避免这些重复计算。这些“记忆”下来的数据，大概可以理解成“历史记录”。我们一般会用一个数组dp来存放这些“历史记录”。问题是，这个数组的意义是什么，里面的值应该怎样更新呢？

LRS问题中dp数组的意义

首先呢，我们需要明确这个dp数组的意义。在我们提到的最长重复子串问题中，\(dp[i][j]\)存储的是以第i和第j个字符结尾的重复子字符串的长度。这样表述还是有点抽象，以一个具体的字符串为例子，如banana。我们会将dp数组初始化如下：

b a n a n a
i \ j 0 1 2 3 4 5
b 0 0 0 0 0 0 0
a 1 0 0 0 0 0 0
n 2 0 0 0 0 0 0
a 3 0 0 0 0 0 0
n 4 0 0 0 0 0 0
a 5 0 0 0 0 0 0

状态转移方程

事实上就是一个\(n*n\)的矩阵（\(n\)为字符串的长度），初始化为0。那么我们从i开始遍历。起初\(i=0\)，那么开始遍历\(j\)，为了避免得到两个完全重合的子字符串，\(j\)的初始值为\(i+1\)，也就是1，随后我们比较\(s[i]\)和\(s[j]\)，如果\(s[i] == s[j]\)，那么我们就把\(dp[i][j]\)在原来的基础上加1。这个原来的基础又分为两种情况：

  1. 在\(i==0\)时，更新数据的过程只是单纯把0变为1，在这个例子中，就是拿出第一个字符b与后面的anana中的每一个字符进行比较，显然后者是没有与前者相匹配的字符，所以第一行的数据依然保持全部为0。
  2. 而当\(i>0\)时，更新数据的过程就应该是\(dp[i][j] == dp[i-1][j-1]+1\)，事实上，\(dp[i-1][j-1]\)就是对前一轮遍历的“记忆”，因为每次遇到字符相等，我们就会想，那这两个字符的前一个字符又是否相同呢？按照这个思路，\(dp\)矩阵在新一轮的更新如下：
b a n a n a
i \ j 0 1 2 3 4 5
b 0 0 0 0 0 0 0
a 1 0 0 0 1 0 1
n 2 0 0 0 0 0 0
a 3 0 0 0 0 0 0
n 4 0 0 0 0 0 0
a 5 0 0 0 0 0 0

通过以上分析，我们可以得到状态转移方程：

\[ dp[i][j] = \left\{ \begin{aligned} &1, \ \ \ \ i =0 \\ &dp[i-1][j-1] + 1, \ \ \ \ i>0 \end{aligned} \right. \] 其中\(j>i\)。 根据这个思路我们把\(dp\)矩阵剩余的数据全部进行更新：

b a n a n a
i \ j 0 1 2 3 4 5
b 0 0 0 0 0 0 0
a 1 0 0 0 1 0 1
n 2 0 0 0 0 2 0
a 3 0 0 0 0 0 3
n 4 0 0 0 0 0 0
a 5 0 0 0 0 0 0

由此，我们就可以得到最长重复子串——ana，及其长度3。C++代码如下：

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
#include<iostream>
#include<string.h>
using namespace std;
string dpLRS(string s)
{
    string ans = "";
    int maxm = 0;
    int sze = s.size();
    int dp[sze][sze];   //新建dp数组
    memset(dp, 0, sizeof(dp));  //初始化dp数组
    for(int i=0; i<sze; i++)
    {
        for(int j=i+1; j<sze; j++)  //从i+1开始遍历
        {
            if(s[i] == s[j])    //若两字符相等
            {
                dp[i][j] = i == 0 ? 1 : dp[i-1][j-1] + 1;   //状态转移方程
                if(dp[i][j] > maxm) //更新答案
                {
                    maxm = dp[i][j];
                    ans = s.substr(i-maxm+1, maxm);
                }
            }
        }
    }
    return ans;
}

int main()
{
    string s,ans;
    cout << "Enter the input string:-\n";
    cin >> s;   //输入字符串
    ans = dpLRS(s);
    cout << "The longest repeating substring is:- " << ans << '\n'; //输出答案
    return 0;
}

重叠问题

读到这里，聪明的你或许已经发现，前面提供的解法貌似有一些问题，比如提到的字符串banana，按道理来讲，我们应该是可以看出最长重复子串应该是an或者na，然而用上面的程序求出来的却是ana，这实际上就是重叠的问题，这个ana来自banana以及banana。那么我们要怎么解决这个问题，使得求出来的答案更加符合我们的直觉呢？就这一点，我们在接下来的内容中会对之前的代码进行修改。

暴力遍历

直接遍历的方法其实很容易改进，注意到我们的\(k\)是从\(i+1\)开始递增的，其实这就是会导致重叠的原因。只要我们把第三层循环的起点设置成\(j+1\)即可，因为第一个字符串\(x\)是以\(s[i]\)开头，\(s[j]\)结尾，只要我们在枚举第二个字符串的时候，把起点设置在\(s[j+1]\)，就不会有重叠的部分了。代码如下：

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
#include<iostream>
#include<string.h>
using namespace std;

string naiveLRS(string s)
{
    int maxm=0; //重复子字符串的最大长度
    string ans = "";
    for(int i=0;i<s.length();i++)
    {
        for(int j=i;j<s.length();j++)
        {
            string x=s.substr(i,j-i+1);  //一个子字符串
            for(int k=j+1;k<s.length();k++) //从j+1开始，避免重叠
            {
                string y=s.substr(k,j-i+1); //另一个与x不相等的子字符串
                if(x == y && x.length() > maxm) //如果这两个字符串相等，并且长度比之前记录的maxm更大，则更新答案
                {
                    maxm = x.length();
                    ans = x;
                }
            }
        }
    }
    return ans;
}

int main()
{
    string s,ans;
    cout << "Enter the input string:-\n";
    cin >> s;   //输入字符串
    ans = naiveLRS(s);
    cout << "The longest repeating substring is:- " << ans << '\n'; //输出答案
    return 0;
}

此时再输入banana，得到的结果就是an了。

dp解法

对于dp解法的改进可能需要稍微绕一点弯子，在更新的过程中，对于同一个子字符串对应的\(dp\)数组的更新，\(i\)和\(j\)是同步进行的，并且我们可以知道这个重复的子字符串的长度即为\(dp[i][j]\)，那么我们就可以知道，第一个字符串的终点即为\(s[i]\)，而第二个字符串的起点，则为\(s[j - dp[i][j]+1]\)，根据\(j-dp[i][j]+1 > i\)，得到\(dp[i][j] < j-i+1\)，那么把这个条件加入到代码中即可。代码如下：

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
#include<iostream>
#include<string.h>
using namespace std;
string dpLRS(string s)
{
    string ans = "";
    int maxm = 0;
    int sze = s.size();
    int dp[sze][sze];   //新建dp数组
    memset(dp, 0, sizeof(dp));  //初始化dp数组
    for(int i=0; i<sze; i++)
    {
        for(int j=i+1; j<sze; j++)  //从i+1开始遍历
        {
            if(s[i] == s[j])    //若两字符相等
            {
                dp[i][j] = i == 0 ? 1 : dp[i-1][j-1] + 1;   //状态转移方程
                if(dp[i][j] > j-i)  dp[i][j] = 1;
                if(dp[i][j] > maxm) //更新答案
                {
                    maxm = dp[i][j];
                    ans = s.substr(i-maxm+1, maxm);
                }
            }
        }
    }
    return ans;
}

int main()
{
    string s,ans;
    cout << "Enter the input string:-\n";
    cin >> s;   //输入字符串
//    ans = naiveLRS(s);
    ans = dpLRS(s);
    cout << "The longest repeating substring is:- " << ans << '\n'; //输出答案
    return 0;
}

一些想法

动态规划和哈希表？

其实要求这个最长重复子串，未必要用到那么难想的动态规划的方法，用哈希的方法同样可以把这个问题解决了。我们可以建立一个\(map<string, int>\)来统计每个子字符串出现的次数，这样的话，我们也是只需要把每个子字符串遍历一遍，进行统计，实时更新即可。时间复杂度和空间复杂度均与动态规划的相同。或许动态规划也是一种以空间换时间的算法吗？

s.substr()的时间复杂度？

查阅了一些网上的回答，说是这个函数只是简单的拷贝，时间复杂度记为\(O(1)\)即可。笔者水平还没有到达阅读stl源码的地步，所以没有在这方面花太多时间，如果您恰巧对此很了解，欢迎您教一教我。

碎碎念

动态规划的算法也算是一个深坑，思想基本都不会变，但是很多题目的具体做法都千变万化，笔者对这方面了解得还是有很多不足之处，待以后学有所成再行分享。写这篇文章只是为了记录一下利用动态规划的思想解决最长重复子串问题的方法，并没有什么关于动态规划的独特见解。算法知识浩如烟海，不过还是如那句老话所说，怕什么真理无穷，进一寸有进一寸的欢喜。