In the Programming Challenge in the Common Child , i have taken a different approach than the general Longest Common Substring problem. The Code is
#include <cmath>
#include <cstdio>
#include <vector>
#include<string>
#include <iostream>
#include <algorithm>
using namespace std;
void max(string a,string b,int n)
{
int count=0,x=-1,prev=0,i,j,k;
for(i=0;i<n;i++)
{
x=-1;
for(j=i;j<n;j++)
{
for(k=x+1;k<n;k++)
{
if(a[j]==b[k])
{
count++;
x=k;
break;
}
}
}
if(prev<count)
{
prev=count;
}
count=0;
}
cout<<prev;
}
int main() {
string a,b;
int n;
cin>>a;
cin>>b;
n=a.length();
max(a,b,n);
return 0;
Taking Smaller TestCases i am being able to get the solution but i am not able to get the solution for longer ones.
What i did is
Input: ABCDEF - Let it be a FBDAMN - Let it be b, as it is inserted in
the code. Output: 2. ie. for BD being the substring.
So what i am doing here is checking the matchable substring for each
substring of a, and print the largest. ie. substring for ABCDEF,
BCDEF,CDEF,DEF,EF,F which signifies the outermost loop here.(loop i)
Now the Second loop matches for each letter in string ie. it iterates
for (1...n),(2...n),(3...n),...,(n), meaning it starts from the letter
i specifies.
Now the third loop iterates through the whole of string B to see if
a[j] matches with any letter in B, if yes then count increments.
Since We can only remove letters from the substring and not jumble it,
i.e. each letter should have the same relative order in both the
strings, I am searching B after the previous letter was found, using
x.
Dry run would be like for the example(arrays from 0 to n-1)
a= abcdef b= fbdamn
when i=0 - the whole string is getting matched abcdef
x=-1 so k iterates from 0 to n-1 So, a=f? a=b? a=d? a=a? count =
count+1; so x is set as 3(position of a). elements after a in A can
only occur after a in B so x=3. therefore k iterates from 4 to 5 b=m?
b=n? c=m?c=n? .... ... ...
now we save the value of previous count if it is greater than counts
before. so maxcount=count and then reset count to 0, and reset
position x=-1.
i=1 i.e string = BCDEF k from 0 to n So, B=F? b=b? count=count+1 //
becomes 1 x is set as 1(position of B) k from 2 to n c=d? c=a?c=m?c=n?
k from 2 to n d=d? count = count+1 // becomes 2 x is set as 2 k from 3
to n e=a?e=m?e=n? k from 3 to n f=a?f=m?f=n? then if max count(prev in
code) greater than current count, then maxcount = count, reset count =
0, x=-1; then it goes like this for CDEF,DEF,EF,F the max substring
here becomes thus 2
Works for the shorter testcases just not for the longer ones.
The test cases it works for are:
OUDFRMYMAW AWHYFCCMQX
With Output 2
Doesnt Work For
WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC
With correct output being 15 and my output being 10. Can Anyone explain to me where am i making a mistake in the