Longest common substring: Difference between revisions
→{{header|langur}}
Langurmonkey (talk | contribs) |
|||
(108 intermediate revisions by 48 users not shown) | |||
Line 1:
{{task}}
;Task:
Write a function that returns the longest common substring of two strings.
Use it within a program that demonstrates sample output from the function, which will consist of the longest common substring between "thisisatest" and "testing123testing".
Note that substrings are consecutive characters within a string. This distinguishes them from subsequences, which is any sequence of characters within a string, even if there are extraneous characters in between them.
Hence, the [[longest common subsequence]] between "thisisatest" and "testing123testing" is "tsitest", whereas the longest common sub''string'' is just "test".
Line 10 ⟶ 17:
*[[Ukkonen’s Suffix Tree Construction]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F longest_common_substring(s1, s2)
V ir = 0
V jr = -1
L(i1) 0 .< s1.len
V? i2 = s2.find(s1[i1])
L i2 != N
V (j1, j2) = (i1, i2)
L j1 < s1.len & j2 < s2.len & s2[j2] == s1[j1]
I j1 - i1 >= jr - ir
(ir, jr) = (i1, j1)
j1++
j2++
i2 = s2.find(s1[i1], i2 + 1)
R s1[ir..jr]
print(longest_common_substring(‘thisisatest’, ‘testing123testing’))</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">BYTE Func Equals(CHAR ARRAY a,b)
BYTE i
IF a(0)#b(0) THEN
RETURN (0)
FI
FOR i=1 TO a(0)
DO
IF a(i)#b(i) THEN
RETURN (0)
FI
OD
RETURN (1)
PROC Lcs(CHAR ARRAY a,b,res)
CHAR ARRAY t(100)
BYTE i,j,len
IF a(0)<b(0) THEN
len=a(0)
ELSE
len=b(0)
FI
WHILE len>0
DO
FOR i=1 to a(0)-len+1
DO
SCopyS(res,a,i,i+len-1)
FOR j=1 to b(0)-len+1
DO
SCopyS(t,b,j,j+len-1)
IF Equals(res,t) THEN
RETURN
FI
OD
OD
len==-1
OD
res(0)=0
RETURN
PROC Test(CHAR ARRAY a,b)
CHAR ARRAY res(100)
Lcs(a,b,res)
PrintF("lcs(""%S"",""%S"")=""%S""%E",a,b,res)
RETURN
PROC Main()
Test("thisisatest","testing123testing")
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_common_substring.png Screenshot from Atari 8-bit computer]
<pre>
lcs("thisisatest","testing123testing")="test"
</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">with Ada.Text_Io;
procedure Longest_Common_Substring is
function Common (Left, Right: String) return String is
Com : array (Left'Range, Right'Range) of Natural := (others => (others => 0));
Longest : Natural := 0;
Last : Natural := 0;
begin
for L in Left'Range loop
for R in Right'Range loop
if Left (L) = Right (R) then
if L > Left'First and R > Right'First then
Com (L, R) := Com (L - 1, R - 1) + 1;
else
Com (L, R) := 1;
end if;
if Com (L, R) > Longest then
Longest := Com (L, R);
Last := L;
end if;
end if;
end loop;
end loop;
return Left (Last - Longest + 1 .. Last);
end Common;
begin
Ada.Text_Io.Put_Line (Common ("thisisatest", "testing123testing"));
end Longest_Common_Substring;</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|Aime}}==
<
test_string(text &g,
{
integer n;
n =
g = cut(l, 0, n);
}
}
longest(text u, v)
{
record r;
text g, l, s;
while (
r[u] = 0;
u = delete(u, 0);
}
while (
if (rsk_lower(r, v, l)) {
test_string(g, v, l);
Line 46 ⟶ 170:
}
}</
<
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">BEGIN
# returns the longest common substring of s and t #
PROC longest common substring = ( STRING s, t )STRING:
BEGIN
STRING s1 = s[ @ 1 ]; # normalise bounds to 1 : ... #
STRING s2 = t[ @ 1 ];
STRING result := "";
INT result len := 0;
FOR i TO UPB s1 DO
FOR j TO UPB s2 DO
IF s1[ i ] = s2[ j ] THEN
INT k := 1;
WHILE INT ik = i + k;
INT jk = j + k;
IF ik > UPB s1 OR jk > UPB s2
THEN FALSE
ELSE s1[ ik ] = s2[ jk ]
FI
DO
k +:= 1
OD;
IF k > result len THEN
# found a longer substring #
result len := k;
result := s1[ i : ( i + k ) - 1 ]
FI
FI
OD
OD;
result
END # longest common substring # ;
# task test case #
print( ( longest common substring( "thisisatest", "testing123testing" ), newline ) )
END</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|APL}}==
<syntaxhighlight lang="apl">lcs←{
sb←∪⊃,/{⌽¨,\⌽⍵}¨,\⍵
match←(sb(∨/⍷)¨⊂⍺)/sb
⊃((⌈/=⊢)≢¨match)/match
}</syntaxhighlight>
{{out}}
<syntaxhighlight lang="apl">
'testing123testing' lcs 'thisisatest'
test</syntaxhighlight>
=={{header|AppleScript}}==
===Iterative===
This allows for the possibility of co-longest substrings, returning one instance of each. If either input string is empty, it's taken as meaning there are no common substrings.
<syntaxhighlight lang="applescript">on LCS(a, b)
-- Identify the shorter string. The longest common substring won't be longer than it!
set lengthA to a's length
set lengthB to b's length
if (lengthA < lengthB) then
set {shorterString, shorterLength, longerString} to {a, lengthA, b}
else
set {shorterString, shorterLength, longerString} to {b, lengthB, a}
end if
set longestMatches to {}
set longestMatchLength to 0
-- Find the longest matching substring starting at each character in the shorter string.
repeat with i from 1 to shorterLength
repeat with j from shorterLength to i by -1
set thisSubstring to text i thru j of shorterString
if (longerString contains thisSubstring) then
-- Match found. If it's longer than the previously found match, or a new string of the same length, remember it.
set matchLength to j - i + 1
if (matchLength > longestMatchLength) then
set longestMatches to {thisSubstring}
set longestMatchLength to matchLength
else if ((matchLength = longestMatchLength) and (thisSubstring is not in longestMatches)) then
set end of longestMatches to thisSubstring
end if
-- Don't bother with the match's own substrings.
exit repeat
end if
end repeat
end repeat
return longestMatches
end LCS</syntaxhighlight>
<syntaxhighlight lang="applescript">LCS("thisisatest", "testing123testing")</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="applescript">{"test"}</syntaxhighlight>
Or:
<syntaxhighlight lang="applescript">LCS("thisisthebesttest", "besting123testing")</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="applescript">{"best", "test"}</syntaxhighlight>
===Functional===
Using library functions wherever possible, for better productivity,
(and for more granular Rosetta comparison):
<syntaxhighlight lang="applescript">------------------ LONGEST COMMON SUBSTRING ----------------
-- longestCommon :: Eq a => [a] -> [a] -> [a]
on longestCommon(a, b)
-- The longest common substring of two given strings.
script substrings
on |λ|(s)
map(my concat, concatMap(my tails, rest of inits(s)))
end |λ|
end script
set {xs, ys} to map(substrings, {a, b})
maximumBy(comparing(my |length|), intersect(xs, ys))
end longestCommon
-------------------------- TEST ---------------------------
on run
longestCommon("testing123testing", "thisisatest")
end run
-------------------- GENERIC FUNCTIONS --------------------
-- comparing :: (a -> b) -> (a -> a -> Ordering)
on comparing(f)
script
set fa to |λ|(a)
set fb to |λ|(b)
else if fa > fb then
end if
end
end script
end comparing
-- concat :: [String] -> String
on concat(xs)
script go
on |λ|(a, x)
a & x
end |λ|
end script
foldl(go, "", xs)
end concat
-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
set lng to length of xs
set acc to {}
tell mReturn(f)
repeat with i from 1 to lng
set acc to acc & (|λ|(item i of xs, i, xs))
end repeat
end tell
return acc
end concatMap
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
set lng to length of xs
end repeat
end tell
end foldl
-- inits :: String -> [String]
on inits(xs)
script charInit
on |λ|(_, i, xs)
end |λ|
end script
{""} & map(charInit, xs)
end inits
-- intersect :: (Eq a) => [a] -> [a] -> [a]
on intersect(xs, ys)
if length of xs < length of ys then
set {shorter, longer} to {xs, ys}
else
set {longer, shorter} to {xs, ys}
end if
if shorter ≠ {} then
set lst to {}
repeat with x in shorter
if longer contains x then set end of lst to contents of x
end repeat
lst
else
{}
end if
end intersect
-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|
-- maximumBy :: (a -> a -> Ordering) -> [a] -> a
on maximumBy(f, xs)
set cmp to mReturn(f)
script max
on |λ|(a, b)
if a is missing value or cmp's |λ|(a, b) < 0 then
b
else
a
end if
end |λ|
end script
foldl(max, missing value, xs)
end maximumBy
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- tails :: String -> [String]
on tails(xs)
set es to characters of xs
script residue
on |λ|(_, i)
items i thru -1 of es
end |λ|
end script
map(residue, es) & {""}
end tails</syntaxhighlight>
{{Out}}
<pre>"test"</pre>
=={{header|Applesoft BASIC}}==
{{trans|BASIC256}}
<syntaxhighlight lang="gwbasic"> 0 A$ = "thisisatest":B$ = "testing123testing": GOSUB 100"LONGEST COMMON SUBSTRING": PRINT R$;: END
100 LET R$ = ""
110 LET A = LEN (A$)
120 LET B = LEN (B$)
130 IF A = 0 OR B = 0 THEN RETURN
140 FOR B = B TO 1 STEP - 1
150 FOR J = B TO 1 STEP - 1
160 FOR K = 1 TO A
170 IF MID$ (A$,K,J) < > LEFT$ (B$,J) THEN NEXT K
180 LET R$ = LEFT$ (B$,J)
190 IF A > K THEN RETURN
200 NEXT J
210 LET B$ = MID$ (B$,2)
220 NEXT B
230 LET R$ = ""
240 RETURN</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">lcs: function [a,b][
lengths: map 0..size a => [map 0..size b => 0]
greatestLength: 0
result: ""
loop.with:'i a 'x [
loop.with:'j b 'y [
if x=y [
if? or? i=0 j=0 ->
lengths\[i]\[j]: 0
else ->
lengths\[i]\[j]: 1 + lengths\[i-1]\[j-1]
if greatestLength < lengths\[i]\[j] [
greatestLength: lengths\[i]\[j]
result: slice a (i-greatestLength)+1 i
]
]
]
]
return result
]
print lcs "thisisatest", "testing123testing"</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|AutoHotkey}}==
===Using Text Comparison===
<
x := i := 1
while StrLen(x)
Line 122 ⟶ 522:
res := StrLen(res) > StrLen(x) ? res : x
return res
}</
Examples:<
Outputs:<pre>test</pre>
===Using RegEx===
<
while pos := RegExMatch(a "`n" b, "(.+)(?=.*\R.*\1)", m, pos?pos+StrLen(m):1)
res := StrLen(res) > StrLen(m1) ? res : m1
return res
}</
Examples:<
Outputs:<pre>test</pre>
=={{header|BaCon}}==
<syntaxhighlight lang="bacon">FUNCTION Common_Sub$(haystack$, needle$)
WHILE LEN(needle$)
FOR x = LEN(needle$) DOWNTO 1
IF INSTR(haystack$, LEFT$(needle$, x)) THEN RETURN LEFT$(needle$, x)
NEXT
needle$ = MID$(needle$, 2)
WEND
EXIT
ENDFUNC
PRINT Common_Sub$("thisisatest", "testing123testing")</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|BASIC}}==
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">CALL LCS("thisisatest", "testing123testing")
END
SUB LCS (a$, b$)
IF LEN(a$) = 0 OR LEN(b$) = 0 THEN PRINT "": EXIT SUB
WHILE LEN(b$)
FOR j = LEN(b$) TO 1 STEP -1
IF INSTR(a$, LEFT$(b$, j)) THEN PRINT LEFT$(b$, j): EXIT SUB
NEXT j
b$ = MID$(b$, 2)
WEND
END SUB</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Run BASIC}}===
{{works with|Just BASIC}}
{{works with|Liberty BASIC}}
<syntaxhighlight lang="lb">call LCS "thisisatest", "testing123testing"
end
sub LCS a$, b$
if len(a$) = 0 or len(b$) = 0 then print "": exit sub
while len(b$)
for j = len(b$) to 1 step -1
if instr(a$, left$(b$, j)) then print left$(b$, j): exit sub
next j
b$ = mid$(b$, 2)
wend
end sub</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">SUB lcs (a$,b$)
IF LEN(a$) = 0 OR LEN(b$) = 0 THEN
PRINT ""
EXIT SUB
END IF
DO WHILE LEN(b$)<>0
FOR j = LEN(b$) TO 1 STEP -1
IF POS(a$,(b$)[1:j])<>0 THEN
PRINT (b$)[1:j]
EXIT SUB
END IF
NEXT j
LET b$ = (b$)[2:maxnum]
LOOP
END SUB
CALL lcs ("thisisatest", "testing123testing")
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">function LCS(a, b)
if length(a) = 0 or length(b) = 0 then return ""
while length(b)
for j = length(b) to 1 step -1
if instr(a, left(b, j)) then return left(b, j)
next j
b = mid$(b, 2)
end while
end function
print LCS("thisisatest", "testing123testing")
end</syntaxhighlight>
=={{header|Bracmat}}==
<syntaxhighlight lang="bracmat"> ( lcs
= X a b x L
. !arg:(?a.?b)
& 0:?L
& :?X
& ( @( !a
: ?
( ?x
& @(!x:? [>!L)
& @(!b:? !x ?)
& @(!x:? [?L:?X)
)
(?&~)
)
| !X
)
)
& out$(lcs$(thisisatest.testing123testing))</syntaxhighlight>
'''Output'''
<pre>test</pre>
=={{header|C}}==
{{trans|Modula-2}}
<
void lcs(const char * const sa, const char * const sb, char ** const beg, char ** const end) {
Line 179 ⟶ 692:
return 0;
}</
{{out}}
<pre>test</pre>
=={{header|C sharp|C#}}==
===Using dynamic programming===
<
namespace LongestCommonSubstring
Line 265 ⟶ 737:
}
}
}</
{{out}}
<pre>
Line 273 ⟶ 745:
===Searching for smaller substrings of a in b===
{{trans|REXX}}
<
using System;
namespace LongestCommonSubstring
Line 307 ⟶ 779:
}
}
}</
'''output''' when using the default inputs:
<pre>
Line 317 ⟶ 789:
===Searching for smaller substrings of a in b (simplified)===
{{trans|zkl}}
<
using System;
namespace LongestCommonSubstring
Line 350 ⟶ 822:
}
}
</syntaxhighlight>
'''output''' when using the default inputs:
<pre>
Line 358 ⟶ 830:
</pre>
=={{header|C++}}==
{{Works with|C++14}}
<syntaxhighlight lang="cpp">#include <string>
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
auto collectSubStrings( const std::string& s, int maxSubLength )
{
int l = s.length();
auto res = std::set<std::string>();
for ( int start = 0; start < l; start++ )
{
int m = std::min( maxSubLength, l - start + 1 );
for ( int length = 1; length < m; length++ )
{
res.insert( s.substr( start, length ) );
}
}
return res;
}
std::string lcs( const std::string& s0, const std::string& s1 )
{
// collect substring set
auto maxSubLength = std::min( s0.length(), s1.length() );
auto set0 = collectSubStrings( s0, maxSubLength );
auto set1 = collectSubStrings( s1, maxSubLength );
// get commons into a vector
auto common = std::vector<std::string>();
std::set_intersection( set0.begin(), set0.end(), set1.begin(), set1.end(),
std::back_inserter( common ) );
// get the longest one
std::nth_element( common.begin(), common.begin(), common.end(),
[]( const std::string& s1, const std::string& s2 ) {
return s1.length() > s2.length();
} );
return *common.begin();
}
int main( int argc, char* argv[] )
{
auto s1 = std::string( "thisisatest" );
auto s2 = std::string( "testing123testing" );
std::cout << "The longest common substring of " << s1 << " and " << s2
<< " is:\n";
std::cout << "\"" << lcs( s1, s2 ) << "\" !\n";
return 0;
}</syntaxhighlight>
{{out}}
<pre>The longest common substring of thisisatest and testing123testing is:
"test" !
</pre>
=={{header|Common Lisp}}==
<syntaxhighlight lang="lisp">
(defun longest-common-substring (a b)
"Return the longest substring common to a and b"
;; Found at https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Common_Lisp
(let ((L (make-array (list (length a) (length b)) :initial-element 0))
(z 0)
(result '()) )
(dotimes (i (length a))
(dotimes (j (length b))
(when (char= (char a i) (char b j))
(setf (aref L i j)
(if (or (zerop i) (zerop j))
1
(1+ (aref L (1- i) (1- j))) ))
(when (> (aref L i j) z)
(setf z (aref L i j)
result '() ))
(when (= (aref L i j) z)
(pushnew (subseq a (1+ (- i z)) (1+ i))
result :test #'equal )))))
result ))
</syntaxhighlight>
{{out}}
<pre>
(longest-common-substring "thisisatest" "testing123testing") => ("test")
</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
include "strings.coh";
sub Contains(s1: [uint8], s2: [uint8]): (r: uint8) is
r := 0;
while [s1] != 0 loop
var a := s1;
var b := s2;
while [b] != 0 and [a] == [b] loop
a := @next a;
b := @next b;
end loop;
if [b] == 0 then
r := 1;
return;
end if;
s1 := @next s1;
end loop;
end sub;
sub LCS(s1: [uint8], s2: [uint8], outbuf: [uint8]) is
if StrLen(s1) < StrLen(s2) then
var temp := s1;
s1 := s2;
s2 := temp;
end if;
var maxlen := StrLen(s2);
var length := maxlen;
while length > 0 loop
var start: intptr := 0;
while start + length <= maxlen loop
MemCopy(s2 + start, length, outbuf);
[outbuf + length + 1] := 0;
if Contains(s1, outbuf) != 0 then
return;
end if;
start := start + 1;
end loop;
length := length - 1;
end loop;
[outbuf] := 0;
end sub;
var lcs: uint8[64];
LCS("thisisatest", "testing123testing", &lcs[0]);
print(&lcs[0]);
print_nl();</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|D}}==
{{trans|C#}}
<
string lcs(string a, string b) {
Line 390 ⟶ 999:
void main() {
writeln(lcs("testing123testing", "thisisatest"));
}</
{{out}}
<pre>test</pre>
=={{header|Delphi}}==
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Longest_Common_Substring;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils;
function lcs(x, y: string): string;
var
n, m, Alength: Integer;
t, common: string;
j: Integer;
k: Integer;
begin
Result := '';
Alength := x.Length;
for j := 0 to Alength - 1 do
for k := Alength - j downto 0 do
begin
common := x.Substring(j, k);
if (y.IndexOf(common) > -1) and (common.Length > Result.Length) then
Result := common;
end;
end;
var
a, b: string;
begin
a := 'thisisatest';
b := 'testing123testing';
if ParamCount = 2 then
begin
if not ParamStr(1).IsEmpty then
a := ParamStr(1);
if not ParamStr(2).IsEmpty then
b := ParamStr(2);
end;
Writeln('string A = ', a);
Writeln('string B = ', b);
Writeln('LCsubstr = ', lcs(a, b));
readln;
end.
</syntaxhighlight>
{{out}}
<pre>
string A = thisisatest123
string B = testing123testing
LCsubstr = test
</pre>
=={{header|Dyalect}}==
Line 398 ⟶ 1,066:
{{trans|Swift}}
<
var (len, end) = (0, 0)
var mat = Array.
var (i, j) = (0, 0)
for sLett in w1 {
for tLett in w2 {
if tLett == sLett {
mat[i + 1][j + 1] = curLen
if curLen > len {
len = curLen
end = i
}
}
Line 418 ⟶ 1,086:
i += 1
}
String(values: w1).
}
func comSubStr(w1, w2) {
return String(lComSubStr(w1.
}
comSubStr("thisisatest", "testing123testing") // "test"</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight>
func$ lcs a$ b$ .
if a$ = "" or b$ = ""
return ""
.
while b$ <> ""
for j = len b$ downto 1
l$ = substr b$ 1 j
for k = 1 to len a$ - j + 1
if substr a$ k j = l$
if len l$ > len max$
max$ = l$
.
break 2
.
.
.
b$ = substr b$ 2 9999
.
return max$
.
print lcs "thisisatest" "testing123testing"
print lcs "thisisatest" "stesting123testing"
print lcs "thisisatestxestinoo" "xxtesting123testing"
</syntaxhighlight>
=={{header|Elixir}}==
{{works with|Elixir|1.3}}
<
def longest_common_substring(a,b) do
alist = to_charlist(a) |> Enum.with_index
Line 450 ⟶ 1,146:
end
IO.puts LCS.longest_common_substring("thisisatest", "testing123testing")</
{{out}}
Line 456 ⟶ 1,152:
test
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2020-07-03}}
<syntaxhighlight lang="factor">USING: io sequences.extras ;
"thisisatest" "testing123testing" longest-subseq print</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
program main
implicit none
call compare('testing123testingthing', 'thisis', 'thi')
call compare('testing', 'sting', 'sting')
call compare('thisisatest_stinger', 'testing123testingthing', 'sting')
call compare('thisisatest_stinger', 'thisis', 'thisis')
call compare('thisisatest', 'testing123testing', 'test')
call compare('thisisatest', 'thisisatest', 'thisisatest')
contains
subroutine compare(a,b,answer)
character(len=*),intent(in) :: a, b, answer
character(len=:),allocatable :: a2, match
character(len=*),parameter :: g='(*(g0))'
integer :: i
a2=a ! should really make a2 the shortest and b the longest
match=''
do i=1,len(a2)-1
call compare_sub(a2,b,match)
if(len(a2).lt.len(match))exit
a2=a2(:len(a2)-1)
enddo
write(*,g) merge('(PASSED)','(FAILED)',answer.eq.match), &
& ' longest match found: "',match,'"; expected "',answer,'"', &
& ' comparing "',a,'" and "',b,'"'
end subroutine
subroutine compare_sub(a,b,match)
character(len=*),intent(in) :: a, b
character(len=:),allocatable :: match
integer :: left, foundat, len_a
len_a=len(a)
do left=1,len_a
foundat=index(b,a(left:))
if(foundat.ne.0.and.len(match).lt.len_a-left+1)then
if(len(a(left:)).gt.len(match))then
match=a(left:)
exit
endif
endif
enddo
end subroutine compare_sub
end program main
</syntaxhighlight>
{{out}}
<pre>
(PASSED) longest match found: "thi"; expected "thi" comparing "testing123testingthing" and "thisis"
(PASSED) longest match found: "sting"; expected "sting" comparing "testing" and "sting"
(PASSED) longest match found: "sting"; expected "sting" comparing "thisisatest_stinger" and "testing123testingthing"
(PASSED) longest match found: "thisis"; expected "thisis" comparing "thisisatest_stinger" and "thisis"
(PASSED) longest match found: "test"; expected "test" comparing "thisisatest" and "testing123testing"
(PASSED) longest match found: "thisisatest"; expected "thisisatest" comparing "thisisatest" and "thisisatest"
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">Function LCS(a As String, b As String) As String
If Len(a) = 0 Or Len(b) = 0 Then Return ""
While Len(b)
For j As Integer = Len(b) To 1 Step -1
If Instr(a, Left(b, j)) Then Return Left(b, j)
Next j
b = Mid(b, 2)
Wend
End Function
Print LCS("thisisatest", "testing123testing")
Sleep</syntaxhighlight>
=={{header|Go}}==
{{trans|C#}}
<
import "fmt"
Line 486 ⟶ 1,262:
func main() {
fmt.Println(lcs("thisisatest", "testing123testing"))
}</
{{out}}
<pre>
Line 493 ⟶ 1,269:
=={{header|Haskell}}==
<
import Data.List (maximumBy, intersect)
Line 508 ⟶ 1,284:
main :: IO ()
main = putStrLn $ longestCommon "testing123testing" "thisisatest"</
{{out}}
<pre>test</pre>
Line 514 ⟶ 1,290:
Or, fusing subStrings as ''tail . inits <=< tails''
<
import Data.List (inits, intersect, maximumBy, tails)
import Data.Ord (comparing)
----------------- LONGEST COMMON SUBSTRING ---------------
longestCommon :: Eq a => [a] -> [a] -> [a]
longestCommon a b =
let pair [x, y] = (x, y)
in maximumBy (comparing length) $
(uncurry intersect . pair) $
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
longestCommon "testing123testing" "thisisatest"</syntaxhighlight>
{{Out}}
<pre>test</pre>
Line 537 ⟶ 1,317:
In other words: this can be suitable for small problems, but you might want something better if you're comparing gigabyte length strings with high commonality.
<
C=. ({.~ 1+$) x=/y
M=. >./ (* * * >. * + (_1&|.)@:|:^:2)^:_ C
N=. >./ M
y {~ (M i. N)-i.-N
)</
Intermedate results:
Line 552 ⟶ 1,332:
Example use:
<
test</
=={{header|Java}}==
<syntaxhighlight lang="java">public class LongestCommonSubstring {
public static void main(String[] args) {
System.out.println(lcs("testing123testing", "thisisatest"));
System.out.println(lcs("test", "thisisatest"));
System.out.println(lcs("testing", "sting"));
System.out.println(lcs("testing", "thisisasting"));
}
static String lcs(String a, String b) {
if (a.length() > b.length())
return lcs(b, a);
String res = "";
for (int ai = 0; ai < a.length(); ai++) {
for (int len = a.length() - ai; len > 0; len--) {
for (int bi = 0; bi <= b.length() - len; bi++) {
if (a.regionMatches(ai, b, bi, len) && len > res.length()) {
res = a.substring(ai, ai + len);
}
}
}
}
return res;
}
}</syntaxhighlight>
<pre>test</pre>
<pre>test</pre>
<pre>sting</pre>
<pre>sting</pre>
=={{header|JavaScript}}==
{{Trans|Haskell}}
<
'use strict';
Line 670 ⟶ 1,485:
// MAIN ---
return main();
})();</
{{Out}}
<pre>test</pre>
Line 708 ⟶ 1,494:
'''Utility functions''':
<
def matrix(m; n; init):
if m == 0 then []
Line 719 ⟶ 1,505:
def set(i;j; value):
setpath([i,j]; value);</
'''Longest Common Substring''':
<
matrix(a|length; b|length; 0) as $lengths
# state: [ $lengths, greatestLength, answer ]
Line 741 ⟶ 1,527:
end
else .
end )) | .[2];</
'''Example''':
<
{{out}}
<
"test"</
=={{header|Julia}}==
{{works with|Julia|
<
l, r, sub_len =
for i
for
contains(s2, SubString(s1, i, j)) || break
end
end
end
return s1[l:r]
end
@show lcs("thisisatest", "testing123testing")</
=={{header|Kotlin}}==
{{trans|Java}}
<
fun lcs(a: String, b: String): String {
Line 785 ⟶ 1,572:
}
fun main(args: Array<String>) = println(lcs("testing123testing", "thisisatest"))</
{{out}}
Line 791 ⟶ 1,578:
test
</pre>
=={{header|Lambdatalk}}==
1) A pure lambdatalk version
<syntaxhighlight lang="scheme">
{def lcs
{def lcs.rec
{lambda {:a :b :w}
{if {or {< {W.length :a} 2} {< {W.length :b} 2} }
then {W.rest :w}
else {if {W.equal? {W.first :a} {W.first :b}}
then {lcs.rec {W.rest :a} {W.rest :b} :w{W.first :a}}
else {let { {:x {lcs.rec :a {W.rest :b} :w}}
{:y {lcs.rec {W.rest :a} :b :w}}
} {if {> {W.length :x} {W.length :y}}
then :x
else :y} }}}}}
{lambda {:a :b}
{lcs.rec :a# :b# #}}}
-> lcs
{lcs testing123testing thisisatest}
-> tsitest // 23000ms
</syntaxhighlight>
2) The pure lambdatalk version is very, very slow, 23000ms.
A much more easier and faster way is to build an interface with the javascript code entry, {{trans|Javascript}}, used as it is.
<syntaxhighlight lang="scheme">
{jslcs testing123testing thisisatest}
-> tsitest // 130ms
{script
// the lcs function code is in the javascript entry
LAMBDATALK.DICT["jslcs"] = function() {
var args = arguments[0].split(" ");
return lcs( args[0], args[1] )
};
}
</syntaxhighlight>
=={{header|langur}}==
{{trans|Julia}}
<syntaxhighlight lang="langur">
val lcs = fn(s1, s2) {
var l, r, sublen = 1, 0, 0
for i of s1 {
for j in i .. len(s1) {
if not matching(s2s(s1, i .. j), s2): break
if sublen <= j - i {
l, r = i, j
sublen = j - i
}
}
}
if r == 0: return ""
s2s s1, l .. r
}
writeln lcs("thisisatest", "testing123testing")
</syntaxhighlight>
{{out}}
<pre>test
</pre>
=={{header|Lobster}}==
{{trans|Go}}
<syntaxhighlight lang="lobster">import std
def lcs(a, b) -> string:
var out = ""
let lengths = map(a.length * b.length): 0
var greatestLength = 0
for(a) x, i:
for(b) y, j:
if x == y:
if i == 0 or j == 0:
lengths[i * b.length + j] = 1
else:
lengths[i * b.length + j] = lengths[(i-1) * b.length + j - 1] + 1
if lengths[i * b.length + j] > greatestLength:
greatestLength = lengths[i * b.length + j]
out = a.substring(i - greatestLength + 1, greatestLength)
return out</syntaxhighlight>
{{trans|C#}}
<syntaxhighlight lang="lobster">import std
def lcs2(a, b) -> string:
var out = ""
let lengths = map(b.length): map(a.length): 0
var greatestLength = 0
for(a) x, i:
for(b) y, j:
if x == y:
if i == 0 or j == 0:
lengths[j][i] = 1
else:
lengths[j][i] = lengths[j-1][i-1] + 1
if lengths[j][i] > greatestLength:
greatestLength = lengths[j][i]
out = a.substring(i - greatestLength + 1, greatestLength)
return out</syntaxhighlight>
=={{header|Maple}}==
<code>StringTools:-LongestCommonSubString()</code> returns the longest common substring of two strings.
<code>StringTools:-CommonSubSequence()</code> returns the longest common subsequence() of two strings.
<
=={{header|Mathematica}}/{{header|Wolfram Language}}==
The function <code>LongestCommonSubsequence</code> returns the longest common substring, and <code>LongestCommonSequence</code> returns the longest common subsequence.
<
{{out}}
<pre>test</pre>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,Write,ReadChar;
Line 862 ⟶ 1,749:
ReadChar
END LCS.</
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim"># Longest common substring.
import sequtils
func lcs(a, b: string): string =
var lengths = newSeqWith(a.len, newSeq[int](b.len))
var greatestLength = 0
for i, x in a:
for j, y in b:
if x == y:
lengths[i][j] = if i == 0 or j == 0: 1 else: lengths[i - 1][j - 1] + 1
if lengths[i][j] > greatestLength:
greatestLength = lengths[i][j]
result = a[(i - greatestLength + 1)..i]
echo lcs("thisisatest", "testing123testing")</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|Pascal}}==
=== using FreePascal ===
{{trans|Delphi}}
{{works with|Free Pascal| 3.2.2 }}
<syntaxhighlight lang="pascal">
PROGRAM LongestCommonSubString.pas;
{$IFDEF FPC}
{$mode objfpc}{$H+}{$J-}{$m+}{$R+}{$T+}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
(*)
Free Pascal Compiler version 3.2.2 [2022/08/01] for x86_64
The free and readable alternative at C/C++ speeds
compiles natively to almost any platform, including raspberry PI *
Can run independently from DELPHI / Lazarus
https://www.freepascal.org/advantage.var
Version without `USES SysUtils, Variants ;` and without `SubStr`, we do not need it here...
(*)
FUNCTION IFF ( Cond: boolean; A, B: string ) : string ;
BEGIN IF ( Cond ) THEN IFF := A ELSE IFF := B ; END ;
FUNCTION lcss( S1, S2: string ) : string ;
VAR
j : Integer = 0 ;
k : Integer = 0 ;
S : string = '' ;
BEGIN
lcss := '' ;
FOR j := 0 TO length ( S1 ) DO BEGIN
FOR k := length ( S1 ) - j DOWNTO 1 DO BEGIN
S := Copy(S1, (j + 1), (k + j + 1)) ;
IF ( pos ( S, S2 ) > 0 ) AND
( length ( S ) > length ( lcss ) ) THEN BEGIN
lcss := S ;
BREAK ;
END ;
END ;
END ;
END ; (*) FUNCTION lcss (*)
VAR
S1: string = 'thisisatest' ;
S2: string = 'testing123testing' ;
BEGIN
IF ParamCount = 2 THEN BEGIN
S1 := IFF( ( ParamStr ( 1 ) > '' ), ParamStr ( 1 ) , S1 );
S2 := IFF( ( ParamStr ( 2 ) > '' ), ParamStr ( 2 ) , S1 );
END;
Writeln ( 'string A = ', S1 ) ;
Writeln ( 'string B = ', S2 ) ;
WriteLn ( Lcss ( S1, S2 ) ) ;
END. (*) Of PROGRAM LongestCommonSubString.pas (*)
(*)
</syntaxhighlight>
<PRE>JPD 2021/06/18
Output:
string A = thisisatest
string B = testing123testing
test
</PRE>(*)
=={{header|Perl}}==
<
use strict ;
use warnings ;
Line 898 ⟶ 1,917:
my $longest = longestCommonSubstr( "thisisatest" ,"testing123testing" ) ;
print "The longest common substring of <thisisatest> and <testing123testing> is $longest !\n" ;
</syntaxhighlight>
{{out}}
<pre>The longest common substring of <thisisatest> and <testing123testing> is test !</pre>
===Alternate letting regex do the work===
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Longest_Common_Substring
use warnings;
my $one = 'thisisatest';
my $two = 'testing123testing';
my @best;
"$one\n$two" =~ /(.+).*\n.*\1(?{ $best[length $1]{$1}++})(*FAIL)/;
print "$_\n" for sort keys %{ $best[-1] };</syntaxhighlight>
{{out}}
test
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">lcs</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">longest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">longest</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">longest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">best</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">lcs</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"thisisatest"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"testing123testing"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">lcs</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"testing123testing"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"thisisatest"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 964 ⟶ 1,970:
=={{header|PicoLisp}}==
<
(setq Str1 (chop Str1) Str2 (chop Str2))
(let Res NIL
Line 980 ⟶ 1,986:
Str2 ) )
Str1 )
(pack Res) ) )</
Test:
<
-> "test"</
=={{header|PowerShell}}==
<
{
if ([String]::IsNullOrEmpty($a) -or [String]::IsNullOrEmpty($b))
{
return ""
}
$startIndex, $size = -1, -1
for ($k = 0;
{
for ($i, $j, $d = $k, 0,
if ($a.Chars($i) -eq
{
$d += 1
if ($size -lt $d)
{
$startIndex = $i - $d + 1
$size = $d
}
}
else
{
$d = 0
}
}
for ($k = 1;
{
for ($i, $j, $d = 0, $k, 0; ($i -lt $a.Length) -and ($j -lt $b.Length); ++$i, ++$j)
if
{
$startIndex = $i - $d + 1
$size = $d
}
}
else
{
$d = 0
}
}
}
if ($size -lt 0)
{
return ""
}
return $a.Substring($startIndex, $size)
}
function Print-Lcs([String]$a, [String]$b)
{
return "lcs $a $b = $(lcs $a $b)"
}
Print-Lcs 'thisisatest' 'testing123testing'
Print-Lcs 'testing' 'sting'
Print-Lcs 'thisisatest_stinger' 'testing123testingthing'
Print-Lcs 'thisisatest_stinger' 'thisis'
Print-Lcs 'testing123testingthing' 'thisis'
Print-Lcs 'thisisatest' 'thisisatest'</syntaxhighlight>
{{out}}
<pre>
lcs thisisatest testing123testing = test
lcs testing sting = sting
lcs thisisatest_stinger testing123testingthing = sting
lcs thisisatest_stinger thisis = thisis
lcs testing123testingthing thisis = thi
lcs thisisatest thisisatest = thisisatest
</pre>
=={{header|Prolog}}==
<
append(_, Ma, A),
append(M, _, Ma),
Line 1,044 ⟶ 2,086:
), AllSubstrings),
longest_list(AllSubstrings, [], 0, LongestSubString),
string_chars(Result, LongestSubString).</
{{out}}
<pre>
Line 1,050 ⟶ 2,092:
Longest = "test".
</pre>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">Procedure.s lcs(a$,b$)
If Len(a$)>Len(b$) : Swap a$,b$ : EndIf
l=Len(a$)
For c=1 To l
For i=1 To 1+l-c
If FindString(b$,Mid(a$,i,c))
res$=Mid(a$,i,c)
EndIf
Next
Next
ProcedureReturn res$
EndProcedure
t1$="testing123testing"
t2$="thisisatest"
Debug lcs(t1$,t2$)</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|Python}}==
===
====Python: Using Indexes====
<syntaxhighlight lang="python">s1 = "thisisatest"
s2 = "testing123testing"
len1, len2 = len(s1), len(s2)
ir, jr = 0,
for i1 in range(len1):
i2 = s2.find(s1[i1])
while i2 >= 0:
j1, j2 = i1
while j1 < len1 and j2 < len2 and s2[j2] == s1[j1]:
if j1-i1 >= jr-ir:
ir, jr = i1, j1
j1 += 1; j2 += 1
i2 = s2.find(s1[i1], i2+1)
print (s1[ir:jr+1])</
{{out}}
<pre>"test"</pre>
====Python: Set of substrings====
From my [https://paddy3118.blogspot.com/2021/02/longest-common-substring-investigation.html explanatory blog post].
<syntaxhighlight lang="python">def _set_of_substrings(s:str) -> set:
"_set_of_substrings('ABBA') == {'A', 'AB', 'ABB', 'ABBA', 'B', 'BA', 'BB', 'BBA'}"
len_s = len(s)
return {s[m: n] for m in range(len_s) for n in range(m+1, len_s +1)}
def _set_of_common_substrings(s:str, common: set) -> set:
"Substrings of s that are also in common"
len_s = len(s)
return {this for m in range(len_s) for n in range(m+1, len_s +1)
if (this := s[m:n]) in common}
def lcs_ss(*strings):
"longest of the common substrings of all substrings of each string"
strings_iter = (s for s in strings)
common = _set_of_substrings(next(strings_iter)) # First string substrings
for s in strings_iter:
if not common:
break
common = _set_of_common_substrings(s, common) # Accumulate the common
return max(common, key= lambda x: len(x)) if common else ''
s0 = "thisisatest_stinger"
s1 = "testing123testingthing"
s2 = "thisis"
ans = lcs_ss(s0, s1)
print(f"\n{repr(s0)}, {repr(s1)} ->> {repr(ans)}")
ans = lcs_ss(s0, s2)
print(f"\n{repr(s0)}, {repr(s2)} ->> {repr(ans)}")
ans = lcs_ss(s1, s2)
print(f"\n{repr(s1)}, {repr(s2)} ->> {repr(ans)}")
ans = lcs_ss(s0, s1, s2)
print(f"\n{repr(s0)}, {repr(s1)}, {repr(s2)} ->> {repr(ans)}")
</syntaxhighlight>
{{out}}
<pre>'thisisatest_stinger', 'testing123testingthing' ->> 'sting'
'thisisatest_stinger', 'thisis' ->> 'thisis'
'testing123testingthing', 'thisis' ->> 'thi'
'thisisatest_stinger', 'testing123testingthing', 'thisis' ->> 'thi'</pre>
===Functional===
Line 1,076 ⟶ 2,188:
Expressed as a composition of pure generic functions:
<syntaxhighlight lang="python">'''Longest common substring'''
from itertools import accumulate, chain
from functools import reduce
# longestCommon :: String -> String -> String
def longestCommon(s1):
'''The longest common substring of
two
def
return
concatMap(tails)(
compose(tail, list, inits)(s)
)
), [s1, s2])
), key=len)
return go
#
def main():
'''Test'''
print(
longestCommon
"testing123testing"
)(
"thisisatest"
)
Line 1,102 ⟶ 2,224:
#
# compose :: ((a -> a), ...) -> (a -> a)
'''Composition, from right to left,
of a series of functions.
'''
def go(f, g):
def fg(x):
return f(g(x))
return fg
return reduce(go, fs, lambda x: x)
# concat :: [String] -> String
def concat(xs):
'''The concatenation of all the elements
in a list or iterable.
'''
return ''.join(xs)
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list over which a function has been
The list monad can be
which wraps its output in a list, (using an empty
list to represent computational failure).
'''
def go(xs):
return chain.from_iterable(map(f, xs))
return go
# inits :: [a] -> [[a]]
def inits(xs):
'''all initial segments of xs, shortest first.'''
return accumulate(chain([[]], xs), lambda a, x: a + [x])
# intersect :: [a] -> [a] -> [a]
def intersect(xs, ys):
'''The ordered intersection of xs and ys.
intersect([1,2,2,3,4])([6,4,4,2]) -> [2,2,4]
'''
s = set(ys)
return
# scanl :: (b -> a -> b) -> b -> [a] -> [b]
def scanl(f):
'''scanl is like reduce, but defines a succession of
intermediate values, building from the left.
def go(a):
def g(xs):
return accumulate(chain([a], xs), f)
return g
return go
# tail :: [a] -> [a]
# tail :: Gen [a] -> [a]
def tail(xs):
'''The elements following the head of a
(non-empty) list.
'''
return xs[1:]
Line 1,160 ⟶ 2,297:
# tails :: [a] -> [[a]]
def tails(xs):
'''All final segments of xs,
longest
'''
return [
xs[i:] for i in
range(0, 1 + len(xs))
# MAIN ---
main()
</syntaxhighlight>
<pre>test</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="Quackery"> [ 0 temp put
0 temp put
tuck dup size times
[ 2dup swap
0 temp put
0 swap witheach
[ unrot
over size
over = iff
[ drop
conclude ]
done
rot dip
[ 2dup peek ]
= tuck * +
dup temp take
max temp put ]
2drop
temp take
dup temp share > iff
[ temp release
i^ temp replace
temp put ]
else drop
behead drop ]
2drop
temp take dip
[ temp take split nip ]
split drop ] is lcs ( $ $ --> $ )
$ "thisisatest" $ "testing123testing" lcs echo$ cr</syntaxhighlight>
{{out}}
<pre>test</pre>
Line 1,174 ⟶ 2,353:
A chance to show off how to use <code>HashTable</code> types in <i>typed/racket</i>
<
(: lcs (String String -> String))
(define (lcs a b)
Line 1,198 ⟶ 2,377:
(module+ test
("thisisatest" . lcs . "testing123testing"))</
{{out}}
Line 1,204 ⟶ 2,383:
<pre>"test"</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub createSubstrings( Str $word --> Array ) {
my $length = $word.chars ;
my @substrings ;
for (0..$length - 1) -> $start {
for (1..$length - $start) -> $howmany {
@substrings.push( $word.substr( $start , $howmany ) ) ;
}
}
return @substrings ;
}
sub findLongestCommon( Str $first , Str $second --> Str ) {
my @substringsFirst = createSubstrings( $first ) ;
my @substringsSecond = createSubstrings( $second ) ;
my $firstset = set( @substringsFirst ) ;
my $secondset = set( @substringsSecond ) ;
my $common = $firstset (&) $secondset ;
return $common.keys.sort({$^b.chars <=> $^a.chars})[0] ; # or: sort(-*.chars)[0]
}
sub MAIN( Str $first , Str $second ) {
say "The longest common substring of $first and $second is " ~
"{findLongestCommon( $first , $second ) } !" ;
}</syntaxhighlight>
{{out}}
<pre>The longest common substring of thisisatest and testing123testing is test !</pre>
=== Functional ===
<syntaxhighlight lang="raku" line>sub substrings ($s) { (flat (0..$_ X 1..$_).grep:{$_ ≥ [+] @_}).map: { $s.substr($^a, $^b) } given $s.chars }
sub infix:<LCS>($s1, $s2) { ([∩] ($s1, $s2)».&substrings).keys.sort(*.chars).tail }
my $first = 'thisisatest';
my $second = 'testing123testing';
say "The longest common substring between '$first' and '$second' is '{$first LCS $second}'.";</syntaxhighlight>
{{out}}
<pre>The longest common substring between 'thisisatest' and 'testing123testing' is 'test'.</pre>
=={{header|Refal}}==
<syntaxhighlight lang"refal">$ENTRY Go {
= <Prout <LCS ('thisisatest') 'testing123testing'>>;
};
LCS {
(e.X) e.L e.X e.R = e.X;
() e.Y = ;
e.X e.Y, e.X: (s.L e.XL),
e.X: (e.XR s.R)
= <Longest (<LCS (e.XL) e.Y>) <LCS (e.XR) e.Y>>;
};
Longest {
(e.X) e.Y, <Lenw e.X>: s.LX e.X2,
<Lenw e.Y>: s.LY e.Y2,
<Compare s.LX s.LY>: '+' = e.X;
(e.X) e.Y = e.Y;
};</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|REXX}}==
<
parse arg a b . /*obtain optional arguments from the CL*/
if a=='' then a= "thisisatest" /*Not specified? Then use the default.*/
if b=='' then b= "testing123testing" /* " " " " " " */
say ' string A ='
say ' string B ='
say ' LCsubstr =' LCsubstr(a, b) /*display the Longest Common Substring.*/
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
LCsubstr: procedure; parse arg x,y,,$; #=
L= length(x); w= length(y) /*placeholders for string length of X,Y*/
if w<L then do; parse arg y,x; L=
end
do j=1 for L while j<=L-# /*step through start points in string X*/
do k=L-j+1 to # by -1 /*step through string lengths. */
_= substr(x, j, k) /*extract a possible common substring. */
if pos(_, y)\==0 then if k># then do; $= _; #= k; end
end /*k*/ /* [↑] determine if string _ is longer*/
end /*j*/ /*#: the current length of $ string.*/
return $ /*$: (null if there isn't common str.)*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,233 ⟶ 2,472:
=={{header|Ring}}==
<
# Project : Longest Common Substring
Line 1,259 ⟶ 2,498:
next
see subend + nl
</syntaxhighlight>
Output:
<pre>
Line 1,267 ⟶ 2,506:
=={{header|Ruby}}==
{{trans|C#}}
<
lengths = Array.new(a.length){Array.new(b.length, 0)}
greatestLength = 0
Line 1,284 ⟶ 2,523:
end
p longest_common_substring("thisisatest", "testing123testing")</
{{out}}
<pre>
"test"
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn longest_common_substring(s1: &str, s2: &str) -> String {
let s1_chars: Vec<char> = s1.chars().collect();
let s2_chars: Vec<char> = s2.chars().collect();
let mut lcs = "".to_string();
for i in 0..s1_chars.len() {
for j in 0..s2_chars.len() {
if s1_chars[i] == s2_chars[j] {
let mut tmp_lcs = s2_chars[j].to_string();
let mut tmp_i = i + 1;
let mut tmp_j = j + 1;
while tmp_i < s1_chars.len() && tmp_j < s2_chars.len() && s1_chars[tmp_i] == s2_chars[tmp_j] {
tmp_lcs = format!("{}{}", tmp_lcs, s1_chars[tmp_i]);
tmp_i += 1;
tmp_j += 1;
}
if tmp_lcs.len() > lcs.len() {
lcs = tmp_lcs;
}
}
}
}
lcs
}
fn main() {
let s1 = "thisisatest";
let s2 = "testing123testing";
let lcs = longest_common_substring(s1, s2);
println!("{}", lcs);
}</syntaxhighlight>
{{out}}
Line 1,292 ⟶ 2,572:
=={{header|Scala}}==
The two algorithms below are Scala optimized versions of the [https://en.wikipedia.org/wiki/Longest_common_substring_problem#Pseudocode Dynamic Programming algorithm pseudocode solution] found on the [https://en.wikipedia.org/wiki/Longest_common_substring_problem "Longest Common Substring" Wikipedia page].
For a more in-depth look at the Scala solution space for this problem, please see [https://stackoverflow.com/a/62071041/501113 this StackOverflow answer].
'''longestCommonSubstringsOptimizedPureFP'''
This algorithm sticks to "Pure" FP (Functional Programming) in that it uses tail recursion while avoiding any use of mutable collections or vars within the function's implementation.
Explore and experiment withing the online Scala playgrounds that run in your favorite browser: [https://scalafiddle.io/sf/gWBcnoX/0 ScalaFiddle (ES a.k.a. JavaScript, non JVM)] or [https://scastie.scala-lang.org/IjwsDgJZSrqqp6x42am6Ug Scastie (remote JVM)].
<syntaxhighlight lang="scala">def longestCommonSubstringsOptimizedPureFP(left: String, right: String): Option[Set[String]] =
if (left.nonEmpty && right.nonEmpty) {
val (shorter, longer) =
if (left.length < right.length) (left, right)
else (right, left)
@scala.annotation.tailrec
def recursive(
indexLonger: Int = 0,
indexShorter: Int = 0,
currentLongestLength: Int = 0,
lengthsPrior: List[Int] = List.fill(shorter.length)(0),
lengths: List[Int] = Nil,
accumulator: List[Int] = Nil
): (Int, List[Int]) =
if (indexLonger < longer.length) {
val length =
if (longer(indexLonger) != shorter(indexShorter)) 0
else lengthsPrior.head + 1
val newCurrentLongestLength =
if (length > currentLongestLength) length
else currentLongestLength
val newAccumulator =
if ((length < currentLongestLength) || (length == 0)) accumulator
else {
val entry = indexShorter - length + 1
if (length > currentLongestLength) List(entry)
else entry :: accumulator
}
if (indexShorter < shorter.length - 1)
recursive(
indexLonger,
indexShorter + 1,
newCurrentLongestLength,
lengthsPrior.tail,
length :: lengths,
newAccumulator
)
else
recursive(
indexLonger + 1,
0,
newCurrentLongestLength,
0 :: lengths.reverse,
Nil,
newAccumulator
)
}
else (currentLongestLength, accumulator)
val (length, indexShorters) = recursive()
if (indexShorters.nonEmpty)
indexShorters
.map {
indexShorter =>
shorter.substring(indexShorter, indexShorter + length)
}
.toSet
)
else None
}
else None
println(longestCommonSubstringsOptimizedPureFP("thisisatest", "testing123testing"))</syntaxhighlight>
{{out}}
<pre>
"Some(Set(test))"
</pre>
'''longestCommonSubstringsOptimizedReferentiallyTransparentFP'''
While this algorithm remains consistent with the FP concept of referential transparency, it does use both a mutable collection and a var within the function's implementation which provide an almost three times performance improvement over the above longestCommonSubstringsOptimizedPureFP implementation.
Explore [http://www.mergely.com/5cLl3LTZ/ this visual diff] to see the changes between the longestCommonSubstringsOptimizedPureFP (above) and longestCommonSubstringsOptimizedReferentiallyTransparentFP (below) implementations
Explore and experiment withing the online Scala playgrounds that run in your favorite browser: [https://scalafiddle.io/sf/gHtMVf1/0 ScalaFiddle (ES a.k.a. JavaScript, non JVM)] or [https://scastie.scala-lang.org/GbMtJwyEQtW8ioabQU6arw Scastie (remote JVM)].
<syntaxhighlight lang="scala">def longestCommonSubstringsOptimizedReferentiallyTransparentFP(left: String, right: String): Option[Set[String]] =
if (left.nonEmpty && right.nonEmpty) {
val (shorter, longer) =
if (left.length < right.length) (left, right)
else (right, left)
val lengths: Array[Int] = new Array(shorter.length) //mutable
@scala.annotation.tailrec
def recursive(
indexLonger: Int = 0,
indexShorter: Int = 0,
currentLongestLength: Int = 0,
lastIterationLength: Int = 0,
accumulator: List[Int] = Nil
): (Int, List[Int]) =
if (indexLonger < longer.length) {
val length =
if (longer(indexLonger) != shorter(indexShorter)) 0
else
if (indexShorter == 0) 1
else lastIterationLength + 1
val newLastIterationLength = lengths(indexShorter)
lengths(indexShorter) = length //mutation
val newCurrentLongestLength =
if (length > currentLongestLength) length
else currentLongestLength
val newAccumulator =
if ((length < currentLongestLength) || (length == 0)) accumulator
else {
val entry = indexShorter - length + 1
if (length > currentLongestLength) List(entry)
else entry :: accumulator
}
if (indexShorter < shorter.length - 1)
recursive(
indexLonger,
indexShorter + 1,
newCurrentLongestLength,
newLastIterationLength,
newAccumulator
)
else
recursive(
indexLonger + 1,
0,
newCurrentLongestLength,
newLastIterationLength,
newAccumulator
)
}
else (currentLongestLength, accumulator)
val (length, indexShorters) = recursive()
if (indexShorters.nonEmpty)
indexShorters
.map {
indexShorter =>
shorter.substring(indexShorter, indexShorter + length)
}
.toSet
)
else None
}
else None
println(longestCommonSubstringsOptimizedReferentiallyTransparentFP("thisisatest", "testing123testing"))</syntaxhighlight>
{{out}}
<pre>
"Some(Set(test))"
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program longest_common_substring;
print(lcs("thisisatest", "testing123testing"));
proc lcs(s1, s2);
if #s1 < #s2 then [s1, s2] := [s2, s1]; end if;
loop for l in [#s2, #s2-1..1] do
loop for s in [1..#s2-l+1] do
if (substr := s2(s..s+l)) in s1 then
return substr;
end if;
end loop;
end loop;
return "";
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>test</pre>
=={{header|Sidef}}==
{{trans|
<
gather {
combinations(word.len+1, 2, {|i,j|
Line 1,343 ⟶ 2,768:
}
say findLongestCommon("thisisatest", "testing123testing")</
{{out}}
<pre>test</pre>
Line 1,349 ⟶ 2,774:
=={{header|Swift}}==
<
S0: Sliceable, S1: Sliceable, T: Equatable where
S0.Generator.Element == T, S1.Generator.Element == T,
Line 1,375 ⟶ 2,800:
func lComSubStr(w1: String, _ w2: String) -> String {
return String(lComSubStr(w1.characters, w2.characters))
}</
Output:
<
=={{header|VBA}}==
<syntaxhighlight lang="vb">
Function Longest_common_substring(string1 As String, string2 As String) As String
Dim i As Integer, j As Integer, temp As String, result As String
For i = 1 To Len(string1)
For j = 1 To Len(string1)
temp = Mid(string1, i, j)
If InStr(string2, temp) Then
If Len(temp) > Len(result) Then result = temp
End If
Next
Next
Longest_common_substring = result
End Function
Sub MainLCS()
Debug.Print Longest_common_substring("thisisatest", "testing123testing")
End Sub
</syntaxhighlight>
{{Out}}
Invoke the script calling "MainLCS".
<pre>
test
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Function lcs(string1,string2)
For i = 1 To Len(string1)
Line 1,397 ⟶ 2,848:
WScript.Echo lcs(WScript.Arguments(0),WScript.Arguments(1))
</syntaxhighlight>
{{Out}}
Line 1,405 ⟶ 2,856:
test
</pre>
=={{header|V (Vlang)}}==
{{trans|C#}}
<syntaxhighlight lang="v (vlang)">fn main()
{
println(lcs("thisisatest", "testing123testing"))
}
fn lcs(a string, b string) string {
mut lengths := map[int]int{}
mut output :=''
mut greatest_length := 0
for i, x in a {
for j, y in b {
if x == y {
if i == 0 || j == 0 {lengths[i * b.len + j] = 1} else {lengths[i * b.len + j] = lengths[(i-1) * b.len + j-1] + 1}
if lengths[i * b.len + j] > greatest_length {
greatest_length = lengths[i * b.len + j]
output += x.ascii_str()
}
}
}
}
return output
}</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="wren">var lcs = Fn.new { |a, b|
var la = a.count
var lb = b.count
var lengths = List.filled(la * lb, 0)
var greatestLength = 0
var output = ""
var i = 0
for (x in a) {
var j = 0
for (y in b) {
if (x == y) {
lengths[i*lb + j] = (i == 0 || j == 0) ? 1 : lengths[(i-1)*lb+j-1] + 1
}
if (lengths[i*lb+j] > greatestLength) {
greatestLength = lengths[i*lb+j]
output = a[i-greatestLength+1..i]
}
j = j + 1
}
i = i + 1
}
return output
}
System.print(lcs.call("thisisatest", "testing123testing"))</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|XPL0}}==
{{trans|C}}
<syntaxhighlight lang "XPL0">string 0;
proc LCS(SA, SB, Beg, End);
char SA, SB;
int Beg, End;
int APos, BPos, Len;
[Beg(0):= 0; End(0):= 0; Len:= 0;
APos:= 0;
while SA(APos) # 0 do
[BPos:= 0;
while SB(BPos) # 0 do
[if SA(APos) = SB(BPos) then
[Len:= 1;
while SA(APos+Len) # 0 and SB(BPos+Len) # 0 and
SA(APos+Len) = SB(BPos+Len) do Len:= Len+1;
];
if Len > End(0) - Beg(0) then
[Beg(0):= SA + APos;
End(0):= Beg(0) + Len;
Len:= 0;
];
BPos:= BPos+1;
];
APos:= APos+1;
];
];
char S1, S2, It;
int Beg, End;
[S1:= "thisisatest";
S2:= "testing123testing";
LCS(S1, S2, @Beg, @End);
for It:= Beg to End-1 do
ChOut(0, It(0));
CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
test
</pre>
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">sub LCS$(a$, b$)
if len(a$) = 0 or len(b$) = 0 then return "" : endif
while len(b$)
for j = len(b$) to 1 step -1
if instr(a$, left$(b$, j)) then return left$(b$, j) : endif
next j
b$ = mid$(b$, 2)
wend
end sub
print LCS$("thisisatest", "testing123testing")
end</syntaxhighlight>
=={{header|zkl}}==
<
if(b.len()<a.len()){ t:=a; a=b; b=t; }
foreach n,m in ([a.len()..1,-1],a.len()-n+1){
Line 1,414 ⟶ 2,987:
}
""
}</
<
{{out}}<pre>test</pre>
|