Brian at 04:49, 29 May 2011

2011-05-29T04:49:55Z

Brian: Created page with "{{Distinguish|Longest common subsequence}} The '''longest common substring''' problem is the problem of finding a string of maximum length which is simultaneously a substring of..."

2011-03-18T22:11:43Z

Created page with "{{Distinguish|Longest common subsequence}} The '''longest common substring''' problem is the problem of finding a string of maximum length which is simultaneously a substring of..."

New page

{{Distinguish|Longest common subsequence}}

The '''longest common substring''' problem is the problem of finding a string of maximum length which is simultaneously a substring of two or more given strings (usually two). For example, the longest common substring of '''atlas''' and '''elastic''' is '''las'''. This problem is much less applicable (in real life) than the more error-tolerant [[longest common subsequence]] problem, but it is theoretically interesting.

==Discussion==
We can observe immediately that this problem is solvable in polynomial time, because a string of length <math>N</math> has <math>O(N^2)</math> substrings, allowing us to simply list all substrings of each string and then find the longest entry(ies) common to both strings. This, however, gives <math>O(N^3+M)</math> time (assuming we have two strings of lengths <math>N</math> and <math>M</math> and we use an efficient [[string search]] algorithm). In addressing the question of whether it is possible to do better, we at first consider three variations on the problem:
* Return ''all'' longest common substrings. There may only be <math>O(\max(n,m))</math> of these, where <math>n</math> is the length of the first string and <math>n</math> is the length of the second. This is because there are only <math>n-x+1</math> substrings of any given length <math>x</math> in the first string, and <math>m-x+1</math> in the second string.
* Return ''any'' longest common substring.
* Return only the ''length'' of a longest common substring.
We shall see that all three variations can be solved in linear time, no matter how many strings are involved.

==Dynamic programming solution==

@@ Line 1: / Line 1: @@
 {{Distinguish|Longest common subsequence}}
-The '''longest common substring''' problem is the problem of finding a string of maximum length which is simultaneously a substring of two or more given strings (usually two). For example, the longest common substring of '''atlas''' and '''elastic''' is '''las'''. This problem is much less applicable (in real life) than the more error-tolerant [[longest common subsequence]] problem, but it is theoretically interesting.
+The '''longest common substring (LCS)''' problem is the problem of finding a string of maximum length which is simultaneously a substring of two or more given strings (usually two). For example, the longest common substring of '''atlas''' and '''elastic''' is '''las'''. This problem is much less applicable (in real life) than the more error-tolerant [[longest common subsequence]] problem, but it is theoretically interesting.
 ==Discussion==
-We can observe immediately that this problem is solvable in polynomial time, because a string of length <math>N</math> has <math>O(N^2)</math> substrings, allowing us to simply list all substrings of each string and then find the longest entry(ies) common to both strings. This, however, gives <math>O(N^3+M)</math> time (assuming we have two strings of lengths <math>N</math> and <math>M</math> and we use an efficient [[string search]] algorithm). In addressing the question of whether it is possible to do better, we at first consider three variations on the problem:
+We can observe immediately that this problem is solvable in polynomial time, because a string of length <math>n</math> has <math>O(n^2)</math> substrings, allowing us to simply list all substrings of each string and then find the longest entry(ies) common to both strings. This, however, gives <math>O(n^3+m)</math> time (assuming we have two strings of lengths <math>n</math> and <math>m</math> and we use an efficient [[string search]] algorithm). In addressing the question of whether it is possible to do better, we at first consider three variations on the problem:
-* Return ''all'' longest common substrings. There may only be <math>O(\max(n,m))</math> of these, where <math>n</math> is the length of the first string and <math>n</math> is the length of the second. This is because there are only <math>n-x+1</math> substrings of any given length <math>x</math> in the first string, and <math>m-x+1</math> in the second string.
+* Return ''all'' LCSes. There may only be <math>O(\min(n,m))</math> of these, where <math>m</math> is the length of the first string and <math>n</math> is the length of the second. This is because there are only <math>m-x+1</math> substrings of any given length <math>x</math> in the first string, and <math>n-x+1</math> in the second string.
-* Return ''any'' longest common substring.
+* Return ''any'' LCS.
-* Return only the ''length'' of a longest common substring.
+* Return only the ''length'' of an LCS.
-We shall see that all three variations can be solved in linear time, no matter how many strings are involved.
+We shall see that all three variations can be solved in linear time, no matter how many strings are given in input.
 ==Dynamic programming solution==

Longest common substring - Revision history

Brian at 04:49, 29 May 2011

Brian: Created page with "{{Distinguish|Longest common subsequence}} The '''longest common substring''' problem is the problem of finding a string of maximum length which is simultaneously a substring of..."