I have a code for Algorithm for finding the largest common substring for n strings but it isn't very effective. Can this Algorithm be rewritten using hash-function? for example Rabin-Carp function?
def f(strings):
sub = ''
if len(strings) > 1 and len(strings[0]) > 0:
for i in range(len(strings[0])):
for j in range(len(strings[0])-i+1):
if j > len(sub) and is_sub(strings[0][i:i+j], strings):
sub = strings[0][i:i+j]
return sub
def is_sub(sub, strings):
if len(strings) < 1 and len(sub) < 1:
return False
for i in range(len(strings)):
if sub not in strings[i]:
return False
return True
n = int(input())
strings = [input() for i in range(n)]
print (f(strings))
I have tried using Rabin-Karp function just for checking if substring is in string. But that didn't work at all. It would be nice? if anybody can suggest efficient solution