求一算法

哦，写完才看到 deitytoday 的答案，他的动态规划比我的好，推荐他的结果

考虑到方便输入输出重定向，就没有显示例如"请输入字符串"的语句，运行后直接输入两个字符串即可。
动态规划的最长公共子串算法，递归输出
时间复杂度O(mnlog(m)) 空间复杂度O(mn)

对例子
abcdefghijklmn
ab1defghklmn2
的输出结果：
3: c, 1
9-10: ij,
15: , 2

#include
#include
#include
using namespace std;

vector str1, str2;
vector > lenmatrix;

int maxstr(char* str1, int len1, char* str2, int len2, char* &combeg1, char* &combeg2){
int maxlen = 0, i, j;
if(len1 == 0 || len2 == 0)return 0;
// init lenmatrix
lenmatrix.resize(len1+1);
lenmatrix[0].assign(len2+1, 0);
for(i = 1; i <= len1; ++i){
lenmatrix[i].resize(len2+1);
lenmatrix[i][0] = 0;
}
// dp
for(i = 1; i <= len1; ++i)
for(j = 1; j <= len2; ++j){
if(str1[i-1] == str2[j-1]){
if((lenmatrix[i][j] = lenmatrix[i-1][j-1] + 1) > maxlen){
maxlen = lenmatrix[i][j];
combeg1 = str1 + i - maxlen;
combeg2 = str2 + j - maxlen;
}
} else
lenmatrix[i][j] = 0;
}
return maxlen;
}

void diffout(char* str1, int len1, char* str2, int len2){
char *beg1, *beg2;
int maxlen = maxstr(str1, len1, str2, len2, beg1, beg2);
if(maxlen == 0){
if(len1 <= 1)
cout << str1 - &::str1[0] + 1 << ":\t";
else
cout << str1 - &::str1[0] + 1 << "-"
<< str1 - &::str1[0] + len1 << ":\t";
cout.write(str1, len1);
cout << ", ";
cout.write(str2, len2);
cout.put('\n');
} else {
int newlen1 = beg1 - str1, newlen2 = beg2 - str2;
if(newlen1 > 0 || newlen2 > 0)
diffout(str1, newlen1, str2, newlen2);
beg1 += maxlen;
beg2 += maxlen;
newlen1 = len1 - (beg1 - str1);
newlen2 = len2 - (beg2 - str2);
if(newlen1 > 0 || newlen2 > 0)
diffout(beg1, newlen1, beg2, newlen2);
}
}

int main(){
string tempstr;
getline(cin, tempstr);
str1.assign(tempstr.begin(), tempstr.end());
getline(cin, tempstr);
str2.assign(tempstr.begin(), tempstr.end());

diffout(&str1[0], str1.size(), &str2[0], str2.size());
return 0;
}

试试这个
那个不同部分的输出方式自便吧...

// 临时最大公共字串
static const int MAX_LEN = 1024;
struct Item
{
char szSubStr[MAX_LEN];
int iTop;
};

int main()
{
// 初始化数据
Item vSameSubStr [2][MAX_LEN] = {0};
int iCurLine = 1;
char sz1[MAX_LEN] = "", sz2[MAX_LEN] = "";
puts("输入两个字符串");
scanf("%[^\n]", sz1);
getchar();
scanf("%[^\n]", sz2);
int iLen1 = strlen(sz1);
int iLen2 = strlen(sz2);

// 求最大公共字串
for (int i = 0; i < iLen1; ++i)
{
int iNextLine = (iCurLine + 1) & 1;

vSameSubStr[iNextLine][0] = vSameSubStr[iCurLine][0];
if (vSameSubStr[iNextLine][0].iTop == 0 && sz1[i] == sz2[0])
{
vSameSubStr[iNextLine][0].szSubStr[vSameSubStr[iNextLine][0].iTop++] = sz2[0];
}

for (int j = 1; j < iLen2; ++j)
{
if (sz1[i] == sz2[j])
{
vSameSubStr[iNextLine][j] = vSameSubStr[iCurLine][j - 1];
vSameSubStr[iNextLine][j].szSubStr[vSameSubStr[iNextLine][j].iTop++] = sz1[i];
}
else
{
vSameSubStr[iNextLine][j] =
vSameSubStr[iNextLine][j - 1].iTop > vSameSubStr[iCurLine][j].iTop ?
vSameSubStr[iNextLine][j - 1] : vSameSubStr[iCurLine][j];
}
}

iCurLine = iNextLine;
}
// 匹配到的结果
char *pMaxSubStr = vSameSubStr[((iLen1 & 1) + 1) & 1][iLen2 - 1].szSubStr;

// 提出两个串不同于公共字串的部分
char *pDif1 = sz1;
char *pDif2 = sz2;
char *pStr1 = sz1;
char *pStr2 = sz2;
while (*pMaxSubStr != 0)
{
while (*pStr1++ != *pMaxSubStr)
{
*pDif1++ = pStr1[-1];
}
while (*pStr2++ != *pMaxSubStr)
{
*pDif2++ = pStr2[-1];
}
pMaxSubStr++;
}
while ((*pDif1++ = *pStr1++) != 0);
while ((*pDif2++ = *pStr2++) != 0);

// 打印不同部分
printf("串1独有部分: %s\n", sz1);
printf("串2独有部分: %s\n", sz2);
}

11月7日更新代码

#include
using namespace std;

const int MAXN = 10000; //字符串最大长度
char a[MAXN], b[MAXN], c[MAXN];
int dp[MAXN][MAXN], lena, lenb, lenc;

int main()
{
scanf("%s%s", a, b);
lena = strlen(a), lenb = strlen(b);
for (int i=lena-1; i>=0; i--)
for (int j=lenb-1; j>=0; j--)
if (a[i] != b[j]) dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
else dp[i][j] = dp[i+1][j+1]+1;
printf("最大公共子串长度：%d\n匹配串：", dp[0][0]);
int i=0, j=0, k, x, t1, t2, t3;
while (i {
if (a[i] == b[j]) c[lenc++] = a[i], i++, j++;
else if (dp[i][j] == dp[i+1][j]) i++;
else j++;
}
c[lenc++] = 0;
printf("%s\n\n对齐之后的字符串:\n", c);
for (i=j=k=x=0; k {
if (a[i]==c[k] && b[j]==c[k]) { putchar(a[i]); continue; }
t1 = t2 = 0;
while (a[i] != c[k]) i++, t1++;
while (b[j] != c[k]) j++, t2++;
t3 = max(t1, t2);
for (t2=i-t1; t2 for (t2=i; t2 x += t3;
putchar(a[i]);
}
putchar('\n');
for (i=j=k=x=0; k {
if (a[i]==c[k] && b[j]==c[k]) { putchar(b[j]); continue; }
t1 = t2 = 0;
while (a[i] != c[k]) i++, t1++;
while (b[j] != c[k]) j++, t2++;
t3 = max(t1, t2);
for (t1=j-t2; t1 for (t1=j; t1 x += t3;
putchar(b[j]);
}
putchar('\n');putchar('\n');
for (i=j=k=x=0; k {
if (a[i]==c[k] && b[j]==c[k]) continue;
t1 = t2 = 0;
while (a[i] != c[k]) i++, t1++;
while (b[j] != c[k]) j++, t2++;
t3 = max(t1, t2);
if (t3 == 1) printf("%d\t'", x+1);
else printf("%d-%d\t'", x+1, x+1+t3);
for (t3=i-t1; t3 printf("' '");
for (t3=j-t2; t3 printf("'\n");
x += max(t1, t2);
}

system("pause");
}

1, i<-0
2, while i3, if a[i] != b[i]
4, out i+1, a[i], b[i]
5, i<-i+1
6, end while
7, if i8, out i+1--length[a], a[i..length[a]-1],
9, else
10, out i+1--length[b], ,b[i..length[b]-1]

自己想的。。。仅供参考