Common substring of length k

Question

I'm trying to write a function that gets 2 strings and an integer 'k' and returns a common substring of both the strings of length k. (If there is more than 1, it returns one at random). There are alot of algorithms online that checks for the LONGEST common substring but I found none that checks the k-length substring.

I think hash tables is the correct way to do it if I want it to be optimized but I couldn't quite get it.

I could only write a function that checks if there is more than 1 k-length sequence in list. Here is what I got:

def repeat(st, k):
    for i in range(len(st) - k + 1):
        for j in range(i + 1, len(st) - k + 1):
            if st[i : i + k] == st[j : j + k]:
                return st[i : i + k]
    return False

I would appreciate ANY help with this... :/

@piokuc: it was wrong to start with. [Edits made during the grace period don't show up in the edit history, so you can't tell that now.] — DSM, May 08 '13 at 18:52

Alfe · Accepted Answer · 2013-05-08T19:26:36.690

3

Simple version is just this:

def common_substr(a, b, k):
  for substr in (a[i:i+k] for i in range(len(a)-k+1)):
    if substr in b:
      return substr

I guess that especially for a very large input strings (e. g. megabytes of text) and large k this might be too inefficient and building up hashes of all possible substrings of length k can improve the speed:

def common_substr(a, b, k):
  substrs = set(a[i:i+k] for i in range(len(a)-k+1))
  for substr in (b[i:i+k] for i in range(len(b)-k+1)):
    if substr in substrs:
      return substr

But I guess that there are much cleverer algorithms around for this. Even the comparably simple strstr() (find string in string) has more efficient solutions than the straight-forward one which everybody can implement.

edited May 08 '13 at 19:26

answered May 08 '13 at 19:20

Alfe

56,346
20
107
159

Thanks alot! Now it seems so simple and iv'e been thinking about this for hours... – Matthew D May 08 '13 at 19:30
If you can't explain it simply, you haven't understood it well enough. —Einstein (supposedly) – Alfe May 08 '13 at 19:31
1

A more efficient algorithm could use a [rolling hash](https://stackoverflow.com/a/1597556/975097) or [suffix tree](https://en.wikipedia.org/wiki/Suffix_tree) to solve this problem. – Anderson Green Apr 10 '22 at 23:25

score 1 · Answer 2 · edited Mar 13 '22 at 19:28

1

This is by no means an efficient or clever solution:

def substrings_of(s, k):
    for i in xrange(0, len(s) - k + 1):
        yield s[i:i+k]

def common_substr(a, b, k):
    for a_s in substrings_of(a, k):
        for b_s in substrings_of(b, k):
            if a_s == b_s:
                return a_s

edited Mar 13 '22 at 19:28

orlp

112,504
36
218
315

answered May 08 '13 at 19:16

Eric

95,302
53
242
374

Common substring of length k

2 Answers2