In the Programming Challenge in the Link
Common Child , i have taken a different approach than the general Longest Common Substring problem.
The Code is given here.
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 abcdefx=-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 2Works 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 code or the logic.