Find common substring between two strings

Question

I d like to compare 2 strings and keep the matched  splitting off where the comparison fails   So if I have 2 strings -  string1   apples string2   appleses  answer   apples   Another example  as the string could have more than one word    string1   apple pie available string2   apple pies  answer   apple pie   I m sure there is a simple Python way of doing this but I can t work it out  any help and explanation appreciated

User · Accepted Answer

Its called Longest Common Substring problem. Here I present a simple, easy to understand but inefficient solution. It will take a long time to produce correct output for large strings, as the complexity of this algorithm is O(N^2).

def longestSubstringFinder(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer

print longestSubstringFinder("apple pie available", "apple pies")
print longestSubstringFinder("apples", "appleses")
print longestSubstringFinder("bapples", "cappleses")

Output

apple pie
apples
apples

User · Answer

def common start sa  sb           returns the longest common substring from the beginning of sa and sb         def  iter            for a  b in zip sa  sb               if a    b                  yield a             else                  return      return    join  iter         gt  gt  gt  common start  apple pie available    apple pies    apple pie      Or a slightly stranger way   def stop iter           An easy way to break out of a generator        raise StopIteration  def common start sa  sb       return    join a if a    b else stop iter   for a  b in zip sa  sb     Which might be more readable as  def terminating cond          An easy way to break out of a generator        if cond          return True     raise StopIteration  def common start sa  sb       return    join a for a  b in zip sa  sb  if terminating a    b

User · Answer

For completeness  difflib in the standard-library provides loads of sequence-comparison utilities  For instance find longest match which finds the longest common substring when used on strings  Example use   from difflib import SequenceMatcher  string1    apple pie available  string2    come have some apple pies   match   SequenceMatcher None  string1  string2  find longest match 0  len string1   0  len string2    print match     - gt  Match a 0  b 15  size 9  print string1 match a  match a   match size      - gt  apple pie print string2 match b  match b   match size      - gt  apple pie

User · Answer

This isn t the most efficient way to do it but it s what I could come up with and it works  If anyone can improve it  please do  What it does is it makes a matrix and puts 1 where the characters match  Then it scans the matrix to find the longest diagonal of 1s  keeping track of where it starts and ends  Then it returns the substring of the input string with the start and end positions as arguments   Note  This only finds one longest common substring  If there s more than one  you could make an array to store the results in and return that Also  it s case sensitive so  Apple pie  apple pie  will return pple pie   def longestSubstringFinder str1  str2   answer       if len str1     len str2       if str1  str2          return str1     else          longer str1         shorter str2 elif  len str1     0 or len str2     0       return    elif len str1  gt len str2       longer str1     shorter str2 else      longer str2     shorter str1  matrix   numpy zeros  len shorter   len longer     for i in range len shorter        for j in range len longer                           if shorter i    longer j               matrix i  j  1  longest 0  start  -1 -1  end  -1 -1      for i in range len shorter -1  -1  -1       for j in range len longer            count 0         begin    i j          while matrix i  j   1               finish  i j              count count 1              if j  len longer -1 or i  len shorter -1                  break             else                  j j 1                 i i 1          i   i-count         if count gt longest              longest count             start begin             end finish             break  answer shorter int start 0    int end 0   1  return answer

User · Answer

def matchingString x y       match        for i in range 0 len x            for j in range 0 len y                k 1               now applying while condition untill we find a substring match and length of substring is less than length of x and y             while  i k  lt   len x  and j k  lt   len y  and x i i k   y j j k                    if len match   lt   len x i i k                       match   x i i k                  k k 1     return match    print matchingString  apple   ale    le print matchingString  apple pie available   apple pies    apple pie

User · Answer

Try   import itertools as it    join el 0  for el in it takewhile lambda t  t 0     t 1   zip string1  string2      It does the comparison from the beginning of both strings

User · Answer

In case we have a list of words that we need to find all common substrings I check some of the codes above and the best was https   stackoverflow com a 42882629 8520109 but it has some bugs for example  histhome  and  homehist   In this case  we should have  hist  and  home  as a result  Furthermore  it differs if the order of arguments is changed  So I change the code to find every block of substring and it results a set of common substrings   main   input   split          a string of words separated by space def longestSubstringFinder string1  string2          Find the longest matching word        answer          len1  len2   len string1   len string2      for i in range len1           for j in range len2               lcs temp 0             match                while   i lcs temp  lt  len1  and  j lcs temp lt len2  and string1 i lcs temp     string2 j lcs temp                    match    string2 j lcs temp                  lcs temp  1                      if  len match   gt  len answer                    answer   match                   return answer  def listCheck main          control the input for finding substring in a list of words        string1   main 0      result          for i in range 1  len main            string2   main i          res1   longestSubstringFinder string1  string2          res2   longestSubstringFinder string2  string1          result append res1          result append res2      result sort       return result  first answer   listCheck main   final answer         for item1 in first answer      to remove some incorrect match     string1   item1     double check   True     for item2 in main          string2   item2         if longestSubstringFinder string1  string2     string1              double check   False     if double check          final answer append string1   print set final answer       main    ABACDAQ BACDAQA ACDAQAW XYZCDAQ    gt  gt  gt    CDAQ   main    homehist histhome    gt  gt  gt    hist    home

User · Answer

One might also consider os path commonprefix that works on characters and thus can be used for any strings  import os common   os path commonprefix   apple pie available    apple pies    assert common     apple pie   As the function name indicates  this only considers the common prefix of two strings

User · Answer

def LongestSubString s1 s2       if len s1  lt len s2            s1 s2   s2 s1            maxsub         for i in range len s2            for j in range len s2  i -1               if s2 i j  in s1 and j-i gt len maxsub                                   return  s2 i j

User · Answer

As if this question doesn t have enough answers  here s another option  from collections import defaultdict def LongestCommonSubstring string1  string2       match    quot  quot      matches   defaultdict list      str1  str2   sorted  string1  string2   key lambda x  len x        for i in range len str1            for k in range i  len str1                cur   match   str1 k              if cur in str2                  match   cur             else                  match    quot  quot                           if match                  matches len match   append match               if not matches          return  quot  quot       longest match   max matches keys                 return matches longest match  0    Some example cases  LongestCommonSubstring  quot whose car  quot    quot this is my car quot    gt    car  LongestCommonSubstring  quot apple pies quot    quot apple  forget apple pie  quot    gt   apple pie

User · Answer

Fix bugs with the first s answer   def longestSubstringFinder string1  string2       answer          len1  len2   len string1   len string2      for i in range len1           for j in range len2               lcs temp 0             match                while   i lcs temp  lt  len1  and  j lcs temp lt len2  and string1 i lcs temp     string2 j lcs temp                    match    string2 j lcs temp                  lcs temp  1             if  len match   gt  len answer                    answer   match     return answer  print longestSubstringFinder  dd apple pie available    apple pies   print longestSubstringFinder  cov basic as cov x gt y rna genes w1000000    cov rna15pcs as cov x gt y rna genes w1000000   print longestSubstringFinder  bapples    cappleses   print longestSubstringFinder  apples    apples

User · Answer

A Trie data structure would work the best  better than DP  Here is the code       class TrieNode      def   init   self           self child    None  26         self endWord   False  class Trie       def   init   self           self root   self getNewNode        def getNewNode self           return TrieNode        def insert self value           root   self root           for i character in enumerate value               index   ord character  - ord  a               if not root child index                   root child index    self getNewNode               root   root child index           root endWord   True       def search self value           root   self root          for i character in enumerate value               index   ord character  - ord  a               if not root child index                   return False             root   root child index          return root endWord  def main            Input keys  use only  a  through  z  and lower case       keys     the   anaswe        output     Not present in trie                 Present in trie           Trie object      t   Trie           Construct trie      for key in keys           t insert key          Search for different keys      print     ----     format  the  output t search  the           print     ----     format  these  output t search  these           print     ----     format  their  output t search  their           print     ----     format  thaw  output t search  thaw        if   name         main          main      Let me know in case of doubts

User · Answer

Return the comman longest substring    def longestSubString str1  str2       longestString          maxLength   0     for i in range 0  len str1            if str1 i  in str2              for j in range i   1  len str1                    if str1 i j  in str2                      if len str1 i j    gt  maxLength                           maxLength   len str1 i j                           longestString    str1 i j  return longestString

User · Answer

The same as Evo s  but with arbitrary number of strings to compare   def common start  strings           Returns the longest common substring         from the beginning of the  strings              def  iter            for z in zip  strings               if z count z 0      len z      check all elements in  z  are the same                 yield z 0              else                  return      return    join  iter

User · Answer

Returns the first longest common substring   def compareTwoStrings string1  string2       list1   list string1      list2   list string2       match          output          length   0      for i in range 0  len list1             if list1 i  in list2              match append list1 i                for j in range i   1  len list1                     if    join list1 i j   in string2                      match append    join list1 i j                     else                      continue         else              continue      for string in match           if length  lt  len list string                length   len list string               output   string          else              continue      return output

User · Answer

This is the classroom problem called  Longest sequence finder   I have given some simple code that worked for me  also my inputs are lists of a sequence which can also be a string   def longest substring list1 list2       both        if len list1  gt len list2           small list2         big list1     else          small list1         big list2     removes 0     stop 0     for i in small          for j in big              if i  j                  removes  1                 if stop  1                      break             elif i  j                  both append i                  for q in range removes 1                       big pop 0                  stop 1                 break         removes 0     return both

User · Answer

This script requests you the minimum common substring length and gives all common substrings in two strings  Also  it eliminates shorter substrings that longer substrings include already  def common substrings str1 str2       len1 len2 len str1  len str2       if len1  gt  len2          str1 str2 str2 str1         len1 len2 len2 len1      min com   int input  Please enter the minumum common substring length              cs array        for i in range len1 min com-1 -1           for k in range len1-i 1               if  str1 k i k  in str2                   flag 1                 for m in range len cs array                        if str1 k i k  in cs array m                        print str1 k i k                           flag 0                         break                 if flag  1                      cs array append str1 k i k       if len cs array           print cs array      else          print  There is no any common substring according to the parametres given    common substrings  ciguliuana   ciguana   common substrings  apples   appleses   common substrings  apple pie available   apple pies

User · Answer

First a helper function adapted from the itertools pairwise recipe to produce substrings   import itertools def n wise iterable  n   2          n   2 - gt   s0 s1    s1 s2    s2  s3            n   3 - gt   s0 s1  s2    s1 s2  s3    s2  s3  s4              a   itertools tee iterable  n      for x  thing in enumerate a 1             for   in range x 1               next thing  None      return zip  a    Then a function the iterates over substrings  longest first  and tests for membership    efficiency not considered   def foo s1  s2          Finds the longest matching substring               the longest matching substring can only be as long as the shortest string      which string is shortest      shortest  longest   sorted  s1  s2   key   len       iterate over substrings  longest substrings first     for n in range len shortest  1  2  -1           for sub in n wise shortest  n               sub      join sub              if sub in longest                   return the first one found  it should be the longest                 return sub  s    fdomainster  t    exdomainid  print foo s t        gt  gt  gt   domain  gt  gt  gt

User · Answer

def LongestSubString s1 s2       left   0     right  len s2      while left lt right           if s2 left  not in s1               left   left 1         else              if s2 left right  not in s1                   right   right - 1             else                  return s2 left right    s1    pineapple  s2    applc  print LongestSubString s1 s2

[python] Find common substring between two strings

Examples related to python

Examples related to string

Examples related to algorithm

Examples related to time-complexity

Examples related to dynamic-programming