动态规划与最长重复子串
时间: 2023-11-17 19:02:00 浏览: 36
动态规划是一种解决问题的算法思想,它通常用于优化问题,通过将问题分解为子问题并重复利用已经解决的子问题的解来解决原问题。而最长重复子串问题是指在一个字符串中找到最长的重复子串,即至少出现两次的子串中最长的一个。这个问题可以通过动态规划来解决。
具体来说,可以使用一个二维数组dp[i][j]来表示以第i个字符结尾的子串和以第j个字符结尾的子串的最长公共前缀的长度。如果第i个字符和第j个字符相同,则dp[i][j]=dp[i-1][j-1]+1,否则dp[i][j]=0。最后,最长重复子串的长度就是所有dp[i][j]中的最大值。
另外,需要注意的是,最长重复子串只能从dp[i-1]或者dp[i-1][j-1]推导而来,因为如果从dp[i][j-1]推导而来,那么得到的就是最长公共子序列,而不是最长重复子串。
相关问题
C++用KMP算法实现最长重复子串
好的,让我来解答你的问题。KMP算法是一种用来匹配字符串的算法,它的核心是计算出每个字符前缀的最长相同前缀和后缀的长度值,这个值可以帮助我们在匹配过程中避免重复比较已经匹配过的字符。在使用KMP算法实现最长重复子串时,我们可以通过不断缩小待查找字符串的长度,找到具有最长相同前缀和后缀的字符串。
代码实现如下:
```
#include <cstring>
int getNext(const char *s, int m, int *next) {
next[0] = -1;
int k = -1;
for (int i = 1; i < m; i++) {
while (k >= 0 && s[k + 1] != s[i]) {
k = next[k];
}
if (s[k + 1] == s[i]) {
k++;
}
next[i] = k;
}
}
int longestRepeatSubstring(const char *s) {
int n = strlen(s);
int next[n];
getNext(s, n, next);
int ans = -1;
for (int i = 0; i < n; i++) {
int j = next[i];
if (j >= 0 && i - j > ans) {
ans = i - j;
}
}
return ans;
}
```
在上述代码中,getNext函数用于计算最长相同前缀和后缀的长度值,使用了KMP算法的核心思想。在最后的longestRepeatSubstring函数中,我们通过遍历每个字符串前缀,找到具有最长相同前缀和后缀的字符串,并返回它的长度。
希望我的回答对你有所帮助!
动态规划(最长公共子序列)
动态规划(Dynamic Programming)是一种常用的算法思想,它通过将原问题分解为若干个子问题的解来求解原问题。在进行子问题的求解时,动态规划会保存已经求解过的子问题的结果,以便后续使用。这样,可以避免重复计算,提高算法的效率。
最长公共子序列(Longest Common Subsequence,简称LCS)是一个经典的动态规划问题。给定两个字符串S和T,求它们的最长公共子序列的长度。子序列是指从原序列中删除若干个元素后得到的序列,而不要求删除的元素的位置相邻。
我们可以定义一个二维数组dp[i][j],表示S的前i个字符和T的前j个字符的最长公共子序列的长度。则有以下状态转移方程:
- 当S[i]==T[j]时,dp[i][j] = dp[i-1][j-1] + 1;
- 当S[i]!=T[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
其中,当S[i]==T[j]时,表示S的第i个字符和T的第j个字符都在最长公共子序列中,那么这个最长公共子序列的长度就是S的前i-1个字符和T的前j-1个字符的最长公共子序列的长度再加上1。当S[i]!=T[j]时,表示S的第i个字符和T的第j个字符不可能同时在最长公共子序列中,那么最长公共子序列的长度就是S的前i-1个字符和T的前j个字符的最长公共子序列的长度,或者是S的前i个字符和T的前j-1个字符的最长公共子序列的长度中的较大值。
最终,最长公共子序列的长度就是dp[m][n],其中m和n分别是S和T的长度。
代码实现如下:
```python
def longest_common_subsequence(S, T):
m, n = len(S), len(T)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if S[i-1] == T[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
```
时间复杂度为O(mn),空间复杂度为O(mn)。