Simple & straight classical LCS algorithm : Source code: #include<bits/stdc++.h> using namespace std; int l1,l2,dp[1003][1003]; char s1[1003],s2[1003]; int len_LCS(int i,int j) { if(i==l1 or j==l2) return 0; if(dp[i][j]!=-1) return dp[i][j]; int ans=0; if(s1[i]==s2[j]) { ans=1+len_LCS(i+1,j+1); } else { int val1=len_LCS(i+1,j); int val2=len_LCS(i,j+1); ans=max(val1,val2); } return dp[i][j]=ans; } int main() { while(gets(s1) && gets(s2)) { memset(dp,-1,sizeof(dp)); l1=strlen(s1); l2=strlen(s2); printf("%d\n",len_LCS(0,0)); } return ...
Comments
Post a Comment