?? lcs存路徑p2264.cpp
字號(hào):
/*
poj 2264 比較經(jīng)典的 LCS 存路徑問(wèn)題,
sunmoonstar_love 極力推薦
*/
#include <iostream>
#include <string>
using namespace std;
int f[2][71],i,j,n,la,lb,t;
string a,b,s[2][71],tmp;
int main()
{
while(cin>>a>>b)
{
la = a.length();
lb = b.length();
for(i=0; i<71; i++)
{
s[0][i]=s[1][i]="";
f[0][i]=f[1][i] = 0;
}
for(i=1; i<=la; i++)
{
for(j=1; j<=lb; j++)
{
if(a[i-1]==b[j-1])
{
f[i%2][j] = f[(i+1)%2][j-1]+1;
s[i%2][j] = s[(i+1)%2][j-1]+a[i-1];
}
else
{
f[i%2][j] = f[(i+1)%2][j];
s[i%2][j] = s[(i+1)%2][j];
if(f[i%2][j]<f[i%2][j-1])
{
f[i%2][j] = f[i%2][j-1];
s[i%2][j] = s[i%2][j-1];
}
}
}
}
tmp = s[la%2][lb];
i = 0;j=0;t=0;
while(i<la)
{
if(a[i]!=tmp[t])
{
cout<<a[i];
i++;
}
else
{
while(j<lb&&b[j]!=tmp[t])
{
cout<<b[j];
j++;
}
if(j==lb)
break;
cout<<tmp[t++];
j++; i++;
}
}
if(i==la&&j!=lb)
{
while(j<lb)
cout<<b[j++];
}
if(j==lb&&i!=la)
{
while(i<la)
cout<<a[i++];
}
cout<<endl;
a = b = "";
}
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -