SequenceMatcher in Python for Longest Common Substring

Last Updated : 24 Mar, 2023

Given two strings ‘X’ and ‘Y’, print the longest common sub-string. Examples:

Input :  X = "GeeksforGeeks", 
         Y = "GeeksQuiz"
Output : Geeks

Input : X = "zxabcdezy", 
        Y = "yzabcdezx"
Output : abcdez

We have existing solution for this problem please refer Print the longest common substring link. We will solve problem in python using SequenceMatcher.find_longest_match() method.

How SequenceMatcher.find_longest_match(aLow,aHigh,bLow,bHigh) method works ?

First we initialize SequenceMatcher object with two input string str1 and str2, find_longest_match(aLow,aHigh,bLow,bHigh) takes 4 parameters aLow, bLow are start index of first and second string respectively and aHigh, bHigh are length of first and second string respectively. find_longest_match() returns named tuple (i, j, k) such that a[i:i+k] is equal to b[j:j+k], if no blocks match, this returns (aLow, bLow, 0).

Implementation:

Python3

# Function to find Longest Common Sub-string 
  
from difflib import SequenceMatcher 
  
def longestSubstring(str1,str2): 
  
     # initialize SequenceMatcher object with  
     # input string 
     seqMatch = SequenceMatcher(None,str1,str2) 
  
     # find match of longest sub-string 
     # output will be like Match(a=0, b=0, size=5) 
     match = seqMatch.find_longest_match(0, len(str1), 0, len(str2)) 
  
     # print longest substring 
     if (match.size!=0): 
          print (str1[(match.a: match.a + match.size)])  
     else: 
          print ('No longest common sub-string found') 
  
# Driver program 
if __name__ == "__main__": 
    str1 = 'GeeksforGeeks'
    str2 = 'GeeksQuiz'
    longestSubstring(str1,str2) 

Output

Geeks

S

Shashank Mishra

Improve

Python Program for Longest Common Subsequence

Similar Reads

Longest substring whose any non-empty substring not prefix or suffix of given String

Given a string S of length N, the task is to find the length of the longest substring X of the string S such that: No non-empty substring of X is a prefix of S.No non-empty substring of X is a suffix of S.If no such string is possible, print −1. Examples: Input: S = "abcdefb"Output: 4Explanation: cdef is the substring satisfying the conditions. Inp

Longest Substring of A that can be changed to Substring of B in at most T cost

Given two strings A and B of the same length and two positive integers K and T. The task is to find the longest substring of A that can be converted to the same substring at the same position in B in less than or equal to T cost. Converting any character of A to any other character costs K units. Note: If multiple valid substrings are possible then

Longest Common Substring (Space optimized DP solution)

Given two strings 'X' and 'Y', find the length of longest common substring. Expected space complexity is linear.Examples : Input : X = "GeeksforGeeks", Y = "GeeksQuiz" Output : 5 The longest common substring is "Geeks" and is of length 5. Input : X = "abcdxyz", Y = "xyzabcd" Output : 4 The longest common substring is "abcd" and is of length 4. We h

Longest Common Substring with max XOR

Given two strings s1 and s2, the task is to find the length of the longest common substring of s1 and s2 such that the XOR is maximum. Examples: Input: s1 = "79567", s2 = "56779"Output: 2Explanation: The longest common substring with a max XOR is "79", which has an XOR of 14 and a length is 2. Input: s1 = "123456", s2 = "8762347"Output: 3Explanatio

Find the Longest Common Substring using Binary search and Rolling Hash

Given two strings X and Y, the task is to find the length of the longest common substring. Examples: Input: X = “GeeksforGeeks”, y = “GeeksQuiz” Output: 5 Explanation: The longest common substring is “Geeks” and is of length 5. Input: X = “abcdxyz”, y = “xyzabcd” Output: 4 Explanation: The longest common substring is “abcd” and is of length 4. Inpu

Longest Common Substring | DP-29

Given two strings 'X' and 'Y', find the length of the longest common substring. Examples : Input : X = "GeeksforGeeks", y = "GeeksQuiz" Output : 5 Explanation:The longest common substring is "Geeks" and is of length 5. Input : X = "abcdxyz", y = "xyzabcd" Output : 4 Explanation:The longest common substring is "abcd" and is of length 4. Input : X

Suffix Tree Application 5 - Longest Common Substring

Given two strings X and Y, find the Longest Common Substring of X and Y.Naive [O(N*M2)] and Dynamic Programming [O(N*M)] approaches are already discussed here. In this article, we will discuss a linear time approach to find LCS using suffix tree (The 5th Suffix Tree Application). Here we will build generalized suffix tree for two strings X and Y as

Print the longest common substring

Given two strings ‘X’ and ‘Y’, print the length of the longest common substring. If two or more substrings have the same value for the longest common substring, then print any one of them. Examples: Input : X = "GeeksforGeeks", Y = "GeeksQuiz" Output : Geeks Input : X = "zxabcdezy", Y = "yzabcdezx" Output : abcdez We have discussed a solution to fi

Longest Common Substring in an Array of Strings

We are given a list of words sharing a common stem i.e the words originate from same word for ex: the words sadness, sadly and sad all originate from the stem 'sad'. Our task is to find and return the Longest Common Substring also known as stem of those words. In case there are ties, we choose the smallest one in alphabetical order. Examples: Input

Longest common substring in binary representation of two numbers

Given two integers n and m. Find the longest contiguous subset in binary representation of both the numbers and their decimal value. Example 1: Input : n = 10, m = 11 Output : 5 Explanation : Binary representation of 10 -> 1010 11 -> 1011 longest common substring in both is 101 and decimal value of 101 is 5 Example 2: Input : n = 8, m = 16 Ou

Article Tags :

Practice Tags :