how to find largest substring common to both strings is

general
1

ESC101 is a course on programming
Mr C teaches ESC101 which is a course on programming

OUTPUT:
27

1 Like
2

Please share the constraints of the question. What is the maximum size of the string? (Most probably around 100?)

3

I have a O(n^2*logn) approach which will pass because n\le1000 . But it is beyond the scope of ESC101A. But I will share it.

First learn hashing here. I prefer to use 2 bases and 2 mods and store them in a pair. Because I think it is difficult to find collisions in that case?

Use 2 loops to iterate over all substring of B and store their hashes in a set. //O(n^2*logn)
Use 2 loops to iterate over all substring of A and search if its hash exist in the set. //O(n^2*logn)

5

@aryanc403 is the above recurrence correct ?,if(A[i]==B[j])
return 1+R(i-1,j-1);( u cant add 1+R(i-1,j-1) because it is common substring not common subsequence) .Please correct me if wrong.

1 Like
7

size of string is less than 1000