LCS.rar_lcs algorithm

#include<iostream> #include<string> using namespace std; /*string lcs_search(string str1, string str2) { if (str1.length() < str2.length()) //保证str1为母串（较长的哪个串) { string strTemp = str1; str1 = str2; str2 = strTemp; } int * sign = new int[str1.length()]; //sign里存储的是母串（str1）每个元素前向能与子串匹配的公共子串数 //比如sign[12]==5;则说明从str1[12]往前5个元素(包括[12])，能与str2的某一段匹配 int length = 0; int end = 0; for (int i = 0; i < str2.length(); i++) { for (int j = str1.length() - 1; j >= 0; j-- ) { if (str2[i] == str1[j]) { if (i == 0 || j == 0) //i==0，则母串的j元素必然只能匹配一个，j==0同理 sign[j] = 1; else //由于该次j匹配，所以子串可以+1 sign[j] = sign[j - 1] + 1; } else //不匹配，则此位置的sign归零 sign[j] = 0; if (sign[j] > length) //结果存储 { length = sign[j]; end = j; } } } delete []sign; return str1.substr(end - length + 1, length); } */ int main() { string str1="abc",str2="ab"; string c; //c=lcs_search(a,b); if (str1.length() < str2.length()) //保证str1为母串（较长的哪个串) { string strTemp = str1; str1 = str2; str2 = strTemp; } cout<<"str2:"<<str2<<" str1: "<<str1<<endl; int * sign = new int[str1.length()]; //sign里存储的是母串（str1）每个元素前向能与子串匹配的公共子串数 //比如sign[12]==5;则说明从str1[12]往前5个元素(包括[12])，能与str2的某一段匹配 int length = 0; int end = 0; for (int i = 0; i < str2.length(); i++) { for (int j = str1.length() - 1; j >= 0; j-- ) { cout<<"str2: "<<str2[i]<<" str1: "<<str1[j]<<endl; if (str2[i] == str1[j]) { if (i == 0 || j == 0) //i==0，则母串的j元素必然只能匹配一个，j==0同理 sign[j] = 1; else //由于该次j匹配，所以子串可以+1 sign[j] = sign[j - 1] + 1; } else //不匹配，则此位置的sign归零 sign[j] = 0; if (sign[j] > length) //结果存储 { length = sign[j]; end = j; } cout<<"j的值："<<j<<" sign[j]: "<<sign[j]<<" length: "<<length<<" end: "<<end<<endl; } } delete []sign; c=str1.substr(end - length + 1, length); cout<<"最长子序列为："<<c<<endl; return 0; }