最长公共子序列问题.txt

来自「算法设计与分析源代码算法设计与分析源代码」· 文本 代码 · 共 58 行

#include<iostream> 
#include<string> 
using namespace std; 
int way[31][31]; 
void main() 
{ 
string w,w1; 
 cin>>w>>w1; 
int j=0,n1,t,n; 
n=w.size(); 
n1=w1.size(); 
w.insert(j,1,'0'); 
w1.insert(j,1,'0'); 
 int find=0; 
 for(int i=1;i<=n;i++) 
 { 
 if(find==0) 
 { 
 if(w1[i]!=w[1]) 
 way[1][i]=0; 
 else 
 { 
 find=1; 
 way[1][i]=1; 
 } 
 } 
 else 
 way[1][i]=1; 
 } 
 for(i=0;i<=n1;i++) 
 way[i][0]=0; 
 for(i=2;i<=n1;i++) 
 { find=0; 
 for(j=1;j<=n;j++) 
 { 
 if(w1[i]==w[j]) 
 { find=j; 
 way[i][j]=way[i-1][j-1]+1; 
 } 
 else 
 { 
 if(find==0) 
 way[i][j]=way[i-1][j]; 
 else 
 { 
 t=1+way[i-1][find-1]; 
 way[i][j]=t>way[i-1][j]?t:way[i-1][j]; 
 } 
 } 
 } 

  
  
  
 } 
 cout<<way[n1][n]<<endl; 
}