Longest common substring: Difference between revisions
m
→{{header|langur}}
Langurmonkey (talk | contribs) |
|||
| (18 intermediate revisions by 11 users not shown) | |||
Line 214:
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}}==
Line 540 ⟶ 551:
<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}}==
Line 846 ⟶ 916:
=={{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#}}
Line 973 ⟶ 1,094:
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}}==
Line 1,388 ⟶ 1,537:
{{works with|Julia|1.5}}
<syntaxhighlight lang="julia">function lcs(s1::AbstractString, s2::AbstractString)::String
l, r, sub_len = 1, 0, 0
for i in eachindex(s1)
for j in i:length(s1)
l, r = i, j
sub_len = j - i
Line 1,400 ⟶ 1,548:
end
end
return s1[l:r]
end
Line 1,429 ⟶ 1,577:
<pre>
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>
Line 1,613 ⟶ 1,825:
FOR k := length ( S1 ) - j DOWNTO 1 DO BEGIN
S := Copy(S1
IF ( pos ( S, S2 ) > 0 ) AND
Line 1,637 ⟶ 1,849:
S1: string = 'thisisatest' ;
S2: string = '
Line 2,096 ⟶ 2,308:
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 2,171 ⟶ 2,421:
<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}}==
<syntaxhighlight lang="rexx">/*REXX program determines the LCSUBSTR (Longest Common Substring) via a function. */
Line 2,460 ⟶ 2,731:
"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}}==
Line 2,564 ⟶ 2,856:
</pre>
=={{header|V (Vlang)}}==
{{trans|C#}}
<syntaxhighlight lang="v (vlang)">fn main()
{
println(lcs("thisisatest", "testing123testing"))
Line 2,597 ⟶ 2,889:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var la = a.count
var lb = b.count
Line 2,628 ⟶ 2,920:
</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}}==
Line 2,643 ⟶ 2,977:
print LCS$("thisisatest", "testing123testing")
end</syntaxhighlight>
=={{header|zkl}}==
| |||