Longest Common Substring

Given two strings s1 and s2. The task is to find the length of the longest common substring.

example:

s1=abcdef
s2=zbcdf

Longest Common Substring  => bcd  =>length => 3


c++ implementation: we will use dynamic programming here

y is the no. of test cases:

#include <iostream>
using namespace std;


void lcs(string s1,string s2,int n,int w)
{    
      int t[n+1][w+1];     
   
   
   //fill  0th rows and coloumns with zero.
   for(int i=0;i<=n;i++)      
      t[i][0]=0;
      
   for(int j=0;j<=w;j++)
      t[0][j]=0;
      
      //comparing that particular value  here s1[i-1] and s2[j-1] because of zero indexing
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=w;j++)
           {
               if(s1[i-1]==s2[j-1])           
               t[i][j]=t[i-1][j-1]+1;
               else
               t[i][j]=0;
           }
       }
       
       //lets take some variable to iterate through two dimensional array
       //and find the maximum value  
     int maxi=0 
      for(int i=1;i<=n;i++)
      {
           for(int j=1;j<=w;j++)
            {   if(maxi<t[i][j])
                maxi=t[i][j];
            }
      }
      cout<<maxi;
}
int main() {int y; cin>>y;
while(y--)
{  int n; int w;
   cin>>n>>w;
   string s1;
   string s2;
   cin>>s1>>s2;
   
   
 lcs(s1,s2,n,w);
  cout<<endl;  
}
 return 0;
}