622
最長連續公共子串算法
#include <iostream>
#include <string.h>
using namespace std;
int GetLCSLength(char* str1, char* str2)
{
int length1 = strlen(str1);
int length2 = strlen(str2);
int maxCommonLen = 0; // 公共子串的長度
int endIndex = 0; // 公共子串的最後位置
// 申請內存
int** table = new int*[length1];
for(int i = 0; i < length1; i++)
table[i] = new int[length2];
// 初始化td
for(int i = 0; i < length1; i++)
{
for(int j = 0; j < length2; j++)
{
table[i][j] = str1[i] == str2[j] ? 1 : 0;
}
}
for(int i = 1; i < length1; i++)
{
for(int j = 1; j < length2; j++)
{
if(str1[i] == str2[j])// 左上角的元素值加1作為當前值
table[i][j] = table[i-1][j-1] + 1;
if(maxCommonLen < table[i][j])
{
endIndex = j;// 記錄最長公共子串的最後一個字符的下標位置
maxCommonLen = table[i][j];
}
}
}
cout << "最長公共子串:";
for(int i = endIndex-maxCommonLen+1; i <= endIndex; i++)
cout << str2[i];
cout << endl;
// 釋放內存
for(int i = 0; i < length1; i ++)
delete[] table[i];
delete[] table;
return maxCommonLen;
}
int main()
{
char* str1 = "21232523311324";
char* str2 = "312123223445";
char* str3 = "asdfeabcsdfa";
char* str4 = "difabcdi";
cout << GetLCSLength(str1, str2) << endl;
cout << GetLCSLength(str3, str4) << endl;
}
最後更新：2017-04-03 18:52:06