Longest common substring: Difference between revisions

{{trans|Python}}

 

V ir = 0

V jr = -1

R s1[ir..jr]

 

 

{{out}}

<pre>

test

</pre>

 

=={{header|Ada}}==

 

procedure Longest_Common_Substring is

begin

Ada.Text_Io.Put_Line (Common ("thisisatest", "testing123testing"));

{{out}}

<pre>

 

=={{header|Aime}}==

{

integer n;

 

g = cut(l, 0, n);

}

}

 

{

record r;

text g, l, s;

 

r[u] = 0;

u = delete(u, 0);

}

if (rsk_lower(r, v, l)) {

test_string(g, v, l);

}

 

 

=={{header|AppleScript}}==

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.

 

-- Identify the shorter string. The longest common substring won't be longer than it!

set lengthA to a's length

return longestMatches

 

 

{{Out}}

 

Or:

 

{{Out}}

 

===Functional===

Using library functions wherever possible, for better productivity,

(and for more granular Rosetta comparison):

 

-- longestCommon :: Eq a => [a] -> [a] -> [a]

end script

map(residue, es) & {""}

{{Out}}

<pre>"test"</pre>

 

=={{header|Arturo}}==

 

lengths: map 0..size a => [map 0..size b => 0]

greatestLength: 0

if x=y [

if? or? i=0 j=0 ->

else ->

 

result: slice a (i-greatestLength)+1 i

]

]

 

 

{{out}}

=={{header|AutoHotkey}}==

===Using Text Comparison===

x := i := 1

while StrLen(x)

res := StrLen(res) > StrLen(x) ? res : x

return res

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

Outputs:<pre>test</pre>

 

=={{header|BaCon}}==

 

WHILE LEN(needle$)

ENDFUNC

 

{{out}}

<pre>test</pre>

 

 

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

if length(a) = 0 or length(b) = 0 then return ""

while length(b)

 

print LCS("thisisatest", "testing123testing")

 

 

=={{header|Bracmat}}==

= X a b x L

. !arg:(?a.?b)

)

)

'''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) {

 

return 0;

{{out}}

<pre>test</pre>

=={{header|C sharp|C#}}==

===Using dynamic programming===

 

namespace LongestCommonSubstring

}

}

{{out}}

<pre>

===Searching for smaller substrings of a in b===

{{trans|REXX}}

using System;

namespace LongestCommonSubstring

}

}

'''output''' when using the default inputs:

<pre>

===Searching for smaller substrings of a in b (simplified)===

{{trans|zkl}}

using System;

namespace LongestCommonSubstring

}

}

'''output''' when using the default inputs:

<pre>

=={{header|C++}}==

{{Works with|C++14}}

#include <algorithm>

#include <iostream>

std::cout << "\"" << lcs( s1, s2 ) << "\" !\n";

return 0;

{{out}}

<pre>The longest common substring of thisisatest and testing123testing is:

 

=={{header|Common Lisp}}==

(defun longest-common-substring (a b)

"Return the longest substring common to a and b"

result :test #'equal )))))

result ))

{{out}}

<pre>

 

 

=={{header|D}}==

{{trans|C#}}

 

string lcs(string a, string b) {

void main() {

writeln(lcs("testing123testing", "thisisatest"));

{{out}}

<pre>test</pre>

=={{header|Delphi}}==

{{Trans|C#}}

program Longest_Common_Substring;

 

readln;

end.

{{out}}

<pre>

{{trans|Swift}}

 

var (len, end) = (0, 0)

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 {

}

}

i += 1

}

}

func comSubStr(w1, w2) {

}

 

 

=={{header|Elixir}}==

{{works with|Elixir|1.3}}

def longest_common_substring(a,b) do

alist = to_charlist(a) |> Enum.with_index

end

 

 

{{out}}

=={{header|Factor}}==

{{works with|Factor|0.99 2020-07-03}}

 

{{out}}

<pre>

</pre>

 

 

=={{header|FreeBASIC}}==

If Len(a) = 0 Or Len(b) = 0 Then Return ""

While Len(b)

 

Print LCS("thisisatest", "testing123testing")

 

 

=={{header|Go}}==

{{trans|C#}}

 

import "fmt"

func main() {

fmt.Println(lcs("thisisatest", "testing123testing"))

{{out}}

<pre>

 

=={{header|Haskell}}==

import Data.List (maximumBy, intersect)

 

 

main :: IO ()

{{out}}

<pre>test</pre>

Or, fusing subStrings as ''tail . inits <=< tails''

 

import Data.List (inits, intersect, maximumBy, tails)

import Data.Ord (comparing)

main =

putStrLn $

{{Out}}

<pre>test</pre>

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:

Example use:

 

 

=={{header|Java}}==

 

public static void main(String[] args) {

return res;

}

 

<pre>test</pre>

=={{header|JavaScript}}==

{{Trans|Haskell}}

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>test</pre>

 

'''Utility functions''':

def matrix(m; n; init):

if m == 0 then []

 

def set(i;j; value):

 

'''Longest Common Substring''':

matrix(a|length; b|length; 0) as $lengths

# state: [ $lengths, greatestLength, answer ]

end

else .

'''Example''':

{{out}}

 

=={{header|Julia}}==

{{works with|Julia|1.5}}

 

for j in i:length(s1)

l, r = i, j

sub_len = j - i

end

end

end

 

 

=={{header|Kotlin}}==

{{trans|Java}}

 

fun lcs(a: String, b: String): String {

}

 

 

{{out}}

<pre>

test

</pre>

 

=={{header|Lobster}}==

{{trans|Go}}

def lcs(a, b) -> string:

var out = ""

greatestLength = lengths[i * b.length + j]

out = a.substring(i - greatestLength + 1, greatestLength)

{{trans|C#}}

def lcs2(a, b) -> string:

var out = ""

greatestLength = lengths[j][i]

out = a.substring(i - greatestLength + 1, greatestLength)

 

=={{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.

 

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;

 

ReadChar

 

=={{header|Nim}}==

{{trans|Go}}

 

import sequtils

result = a[(i - greatestLength + 1)..i]

 

 

{{out}}

<pre>test</pre>

 

=={{header|Perl}}==

use strict ;

use warnings ;

my $longest = longestCommonSubstr( "thisisatest" ,"testing123testing" ) ;

print "The longest common substring of <thisisatest> and <testing123testing> is $longest !\n" ;

{{out}}

<pre>The longest common substring of <thisisatest> and <testing123testing> is test !</pre>

 

===Alternate letting regex do the work===

 

use strict; # https://rosettacode.org/wiki/Longest_Common_Substring

my @best;

"$one\n$two" =~ /(.+).*\n.*\1(?{ $best[length $1]{$1}++})(*FAIL)/;

{{out}}

test

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(setq Str1 (chop Str1) Str2 (chop Str2))

(let Res NIL

Str2 ) )

Str1 )

Test:

 

=={{header|PowerShell}}==

 

}

}

}

}

}

}

 

{{out}}

<pre>

</pre>

 

=={{header|Prolog}}==

 

append(_, Ma, A),

append(M, _, Ma),

), AllSubstrings),

longest_list(AllSubstrings, [], 0, LongestSubString),

{{out}}

<pre>

 

=={{header|PureBasic}}==

If Len(a$)>Len(b$) : Swap a$,b$ : EndIf

l=Len(a$)

t1$="testing123testing"

t2$="thisisatest"

{{out}}

<pre>test</pre>

===Python: Idiomatic===

====Python: Using Indexes====

s2 = "testing123testing"

len1, len2 = len(s1), len(s2)

j1 += 1; j2 += 1

i2 = s2.find(s1[i1], i2+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].

"_set_of_substrings('ABBA') == {'A', 'AB', 'ABB', 'ABBA', 'B', 'BA', 'BB', 'BBA'}"

len_s = len(s)

ans = lcs_ss(s0, s1, s2)

print(f"\n{repr(s0)}, {repr(s1)}, {repr(s2)} ->> {repr(ans)}")

 

{{out}}

 

Expressed as a composition of pure generic functions:

 

from itertools import accumulate, chain

# MAIN ---

main()

<pre>test</pre>

 

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)

 

(module+ test

 

{{out}}

=={{header|Raku}}==

(formerly Perl 6)

my $length = $word.chars ;

my @substrings ;

say "The longest common substring of $first and $second is " ~

"{findLongestCommon( $first , $second ) } !" ;

{{out}}

<pre>The longest common substring of thisisatest and testing123testing is test !</pre>

 

=== Functional ===

sub infix:<LCS>($s1, $s2) { ([∩] ($s1, $s2)».&substrings).keys.sort(*.chars).tail }

 

my $first = 'thisisatest';

my $second = 'testing123testing';

{{out}}

<pre>The longest common substring between 'thisisatest' and 'testing123testing' is '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 ' LCsubstr =' LCsubstr(a, b) /*display the Longest Common Substring.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

LCsubstr: procedure; parse arg x,y,,$; #= 0 /*LCsubstr: Longest Common Substring. */

end /*k*/ /* [↑] determine if string _ is longer*/

end /*j*/ /*#: the current length of $ string.*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Longest Common Substring

 

next

see subend + nl

Output:

<pre>

=={{header|Ruby}}==

{{trans|C#}}

lengths = Array.new(a.length){Array.new(b.length, 0)}

greatestLength = 0

end

 

 

{{out}}

 

=={{header|Rust}}==

let s1_chars: Vec<char> = s1.chars().collect();

let s2_chars: Vec<char> = s2.chars().collect();

let lcs = longest_common_substring(s1, s2);

println!("{}", lcs);

 

{{out}}

 

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)].

if (left.nonEmpty && right.nonEmpty) {

val (shorter, longer) =

else None

 

 

{{out}}

 

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)].

if (left.nonEmpty && right.nonEmpty) {

val (shorter, longer) =

else None

 

 

{{out}}

"Some(Set(test))"

</pre>

 

=={{header|Sidef}}==

{{trans|Raku}}

gather {

combinations(word.len+1, 2, {|i,j|

}

 

{{out}}

<pre>test</pre>

=={{header|Swift}}==

 

S0: Sliceable, S1: Sliceable, T: Equatable where

S0.Generator.Element == T, S1.Generator.Element == T,

func lComSubStr(w1: String, _ w2: String) -> String {

return String(lComSubStr(w1.characters, w2.characters))

 

Output:

 

 

=={{header|VBA}}==

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

Debug.Print Longest_common_substring("thisisatest", "testing123testing")

End Sub

 

{{Out}}

 

=={{header|VBScript}}==

Function lcs(string1,string2)

For i = 1 To Len(string1)

 

WScript.Echo lcs(WScript.Arguments(0),WScript.Arguments(1))

 

{{Out}}

<pre>

C:\>cscript.exe /nologo lcs.vbs "thisisatest" "testing123testing"

test

</pre>

=={{header|Wren}}==

{{trans|Go}}

var la = a.count

var lb = b.count

}

 

 

{{out}}

</pre>

 

 

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

if len(a$) = 0 or len(b$) = 0 then return "" : endif

while len(b$)

 

print LCS$("thisisatest", "testing123testing")

 

=={{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){

}

""

{{out}}<pre>test</pre>