Algorithm for finding the largest common substring for n strings using Rabin-Karp function

24 views Asked by At

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

0

There are 0 answers