最长重复子数组

要求元素在原数组中连续

例如

• 1 2 3 6 7
• 5 8 1 2 3

此时最长重复子数组就是1 2 3， 长度为3

下面是解法思路：

首先用暴力解法思考，按照每一个元素位依次比较，时间复杂度为n3，包括大量重复计算。将暴力解法的每一步记录在二维数组中， 省略了重复比较，以上例作为参考，二维数组构造如下：

  1 2 3 6 7
5 0 0 0 0 0
8 0 0 0 0 0
1 1 0 0 0 0
2 0 2 0 0 0
3 0 0 3 0 0

从二维数组中可以看出最长子数组为3

推导过程：

令数组一为str1，数组二为str2，则 dp[ i ] [ j ]的数值意义是，以数组str1[ i ]结尾和数组二以str2[ j ]结尾的子数组中重复的数组长度最长为多少。
每次数组移动有两种情况

• 这两个子数组结尾相同
• 这两个子数组结尾不同

如果是相同则在dp[ i - 1 ] [ j - 1 ]的基础上加一，否则归零，因为不接受不连续的相同子数组，这里已经截断。

代码

#include
#include//最长重复子数组
int main() {char str1[30];char str2[30];scanf("%s%s", str1, str2);int arr[10][10];int count1 = strlen(str1);int count2 = strlen(str2);for (int i = 0; i < count1; i ++) {//初始化第一行if (str1[i] == str2[0]) {arr[0][i] = 1;}else {arr[0][i] = 0;	}}for (int i = 0; i < count2; i ++) {//初始化第一列if (str2[i] == str1[0]) {arr[i][0] = 1;}else {arr[i][0] = 0;}}for (int i = 1; i < count2; i ++) {//arr[i][j] = arr[i - 1][j - 1] OR 0for (int j = 1; j < count1; j ++) {if (str1[j] == str2[i]) {arr[i][j] = arr[i - 1][j - 1] + 1;}else {arr[i][j] = 0;}}}int result = 0;for (int i = 0; i < count2; i ++) {for (int j = 0; j < count1; j ++) {if (arr[i][j] > result) {result = arr[i][j];}}}printf("%d", result);return 0;
}

最长公共子序列

要求元素在原数组中不连续

例如

• 1 2 3 6 7 4
• 5 8 1 2 3 4

此时最长重复子数组就是1 2 3 4， 长度为4

下面是解法思路：

首先用暴力解法思考，按照每一个元素位依次比较，时间复杂度为n3，包括大量重复计算。将暴力解法的每一步记录在二维数组中， 省略了重复比较，以上例作为参考，二维数组构造如下：

  1 2 3 6 7 4
5 0 0 0 0 0 0
8 0 0 0 0 0 0
1 1 1 1 1 1 1
2 1 2 2 2 2 2
3 1 2 3 3 3 3
4 1 2 3 3 3 4

从二维数组中可以看出最长子数组为4

推导过程：

令数组一为str1，数组二为str2，则 dp[ i ] [ j ]的数值意义是，以数组str1[ i ]结尾和数组二以str2[ j ]结尾的子数组中重复的数组长度最长为多少。
每次数组移动有两种情况

• 这两个子数组结尾相同
• 这两个子数组结尾不同

如果是相同则在dp[ i - 1 ] [ j - 1 ]的基础上加一，否则变为 MAX {dp[ i ] [ j - 1], dp[ i - 1] [ j ] }，因为接收不连续的子序列，最大值是继承的。

代码

#include
#includeint max(int x, int y) {if (x > y) {return x;}else {return y;}
}int main() {char str1[30];char str2[30];scanf("%s%s", str1, str2);int count1 = strlen(str1);int count2 = strlen(str2);int  arr[30][30];if (str1[0] == str2[0]) {arr[0][0] = 1;}else {arr[0][0] = 0;}for (int i = 1; i < count1; i ++) {//初始化第一行if (str1[i] == str2[0]) {arr[0][i] = 1;}else {arr[0][i] = max(arr[0][i - 1], 0);}}for (int i = 1; i < count2; i ++) {//初始化第一列if (str2[i] == str1[0]) {arr[i][0] = 1;}else {arr[i][0] = max(arr[i - 1][0], 0);}}for (int i = 1; i < count2; i ++) {//推导矩阵for (int j = 1; j if (str1[j] == str2[i]) {arr[i][j] = arr[i - 1][j - 1] + 1;}else {arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);}}}printf("%d", arr[count2 - 1][count1 - 1]);return 0;
}

两个算法的区别

对于最长重复子数组，结果需要连续，所以遇到不一样的字符时需要从0开始。对于后者仅需要相同次序，所以每一个字符继承前端结果。