ESC101 is a course on programming

Mr C teaches ESC101 which is a course on programming

OUTPUT:

27

ESC101 is a course on programming

Mr C teaches ESC101 which is a course on programming

OUTPUT:

27

1 Like

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

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)

@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

size of string is less than 1000