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

@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
4

Yes, I misinterpreted.

5

size of string is less than 1000

6

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)

7

If n\le100 then this approach will pass (given TL is 15s on prutor) for this case only for loops are required nothing more.

O(n^4)
Use 2 loops to iterate over all substring of A.
Use one more loop for staring index of the substring.
And the last loop for comparing the string.

pseudo code -
for i <- 0 to n-1 //O(n)
for j <- i to n-1 { //O(n)
len = j-i+1
for k <- 0 to n-len { //O(n)
compare substring A[i...j] and B[k....k+len-1] and if they are equal and len is less then current maximum length then store it as current maximum.
}
}