## Introduction

Determine the longest common substring from a given string. The naive approach [O(N * M ^ 2)] and Dynamic Programming [O(N * M)] techniques have already been discussed for the calculation of the Longest Common Substring. So first go and read all the approaches from __here__. One linear time strategy based on suffix trees will be discussed in this article which can find the Longest Palindromic Substring in O(N) time.

**Example 1**

**Input**

â€śabcdeâ€ť

â€śabfceâ€ť

**Output**

Longest Common Substring in abcde and abfce is: ab, of length: 2

**Explanation**

There are a lot of common substrings between these two strings like a,b,f, ab but we have to find the longest common substring which is common between these two strings which is ab in this case.

**Example 2**

**Input**

â€śqdefâ€ť

â€śdefqâ€ť

**Output**

3

**Explanation**

There are a lot of common substrings between these two strings like "q", "d", "e", "f", "de", "ef", "def". "def" is the longest common substring. So, the length of the longest common substring between these two substrings will be "3".

## Approach

First, we need to make a generalized suffix tree in linear time for the two given substrings. The Suffix Tree is a compressed trie that stores all of a string's suffixes. Suffix tree has been shown to be quite useful in string-related tasks such as detecting different substrings in a string, pattern matching, and determining the largest palindrome, among others. To read more about suffix trees, you can refer to __here__. To read more about the generalized suffix tree, you can read from __here__. Below is the generalized subtree of two substrings x = ABAB and y = BABA.

The generalized subtree for the given strings is ABAB#BABA$

The generalized subtree for the given strings is ABAB#BABA$. Now, after building a suffix tree, the task is to find the longest common substring. For that, we need to compare the generalized suffix tree between the given two strings. After that, find the common occurrences of the string by traversing the tree deep. Then the most important step is to find the common occurrences and then choose the longest string among them. Let X and Y be two strings containing some common substring. We will construct a generalized suffix tree with delimiters # for X and $ for y.

Then perform the depth-first traversal on the generalized suffix tree formed and count the number of occurrences of # and $ as a tuple(#,$).

Then compare the (#, $) tuple values and choose the longest substring. While we maintain occurrences of # and $ at each node, maintain an array of the max count. If at any internal node the value of the tuple (#,$) is greater than the current, update the entry in the array. In case we get the same maximum tuple value for multiple nodes, compare the length of string for which we are getting the tuple value.

Making use of the suffix tree constructed in linear time using __ukkonenâ€™s algorithm__ we can solve the problem of the longest substring in o(1) time. Below is the detailed algorithm for the given approach.

Also check out - __Substr C++__