longest common string Algorithm
The Longest Common Substring Algorithm is a widely used technique in computer science and bioinformatics, aimed at finding the longest contiguous sequence of characters that appears in two or more input strings. It is a classic problem in computer science, with numerous applications including text comparison, file comparison, and pattern recognition. The problem can be solved using various approaches, such as dynamic programming, suffix trees, or rolling hash functions, each having its own time and space complexity trade-offs.
One popular method to solve the longest common substring problem is by using dynamic programming. This approach involves constructing a table where each cell (i, j) represents the length of the longest common substring ending at positions i and j in the input strings. The table is filled row by row, comparing characters from one string with those from the other, and updating the cell values based on previous results. If the characters at positions i and j match, the value in the cell (i, j) becomes the value in the cell (i-1, j-1) plus one, representing the length of the extended common substring. If the characters do not match, the value in the cell (i, j) is set to zero, indicating the end of a common substring. The maximum value in the table represents the length of the longest common substring, and the corresponding substring can be obtained by backtracking through the table.
#include <iosrteam>
using namespace std;
int max(int a,int b)
{
return (a > b) ? a : b;
}
int main()
{
char str1[]="DEFBCD";
char str2[]="ABDEFJ";
int i,j,k;
int n=strlen(str1)+1;
int m=strlen(str2)+1;
//cout<<n<<" "<<m<<"\n";
int a[m][n];
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(i==0 || j==0)
a[i][j]=0;
else if(str1[i-1] == str2[j-1])
a[i][j]=a[i-1][j-1]+1;
else
a[i][j]=0;
}
}
/*for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
cout<<a[i][j]<<" ";
cout<<"\n";
}*/
int ma=-1;
int indi,indj;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]>ma)
{
ma=a[i][j];
indi=i;
indj=j;
}
}
}
cout<<str1<<"\n";
cout<<str2<<"\n";
cout<<"longest string size = "<<ma/*<<" "<<indi<<" "<<indj*/<<"\n";
for(i=indi-3;i<indi;i++)
cout<<str1[i];
cout<<"\n";
}
