Longest common suffix: Difference between revisions
SqrtNegInf (talk | contribs) (Added Perl example) |
MaiconSoft (talk | contribs) No edit summary |
||
Line 3: | Line 3: | ||
;Task: |
;Task: |
||
The goal is to write a function to find the longest common suffix string amongst an array of strings. |
The goal is to write a function to find the longest common suffix string amongst an array of strings. |
||
=={{header|Delphi}}== |
|||
{{libheader| System.SysUtils}} |
|||
{{libheader| Types}} |
|||
{{Trans|Ring}} |
|||
<lang Delphi> |
|||
program Longest_common_suffix; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
System.SysUtils, |
|||
Types; |
|||
type |
|||
TStringDynArrayHelper = record helper for TStringDynArray |
|||
private |
|||
class function Compare(const s: string; a: TStringDynArray; subSize: integer): |
|||
Boolean; |
|||
public |
|||
function Reverse(value: string): string; |
|||
function LongestSuffix: string; |
|||
function Join(const sep: char): string; |
|||
end; |
|||
{ TStringDynArrayHelper } |
|||
class function TStringDynArrayHelper.Compare(const s: string; a: TStringDynArray; |
|||
subSize: integer): Boolean; |
|||
var |
|||
i: Integer; |
|||
begin |
|||
for i := 0 to High(a) do |
|||
if s <> a[i].Substring(0, subSize) then |
|||
exit(False); |
|||
Result := True; |
|||
end; |
|||
function TStringDynArrayHelper.Join(const sep: char): string; |
|||
begin |
|||
Result := string.Join(sep, self); |
|||
end; |
|||
function TStringDynArrayHelper.LongestSuffix: string; |
|||
var |
|||
ALength: Integer; |
|||
i, lenMin, longest: Integer; |
|||
ref: string; |
|||
begin |
|||
ALength := Length(self); |
|||
// Empty list |
|||
if ALength = 0 then |
|||
exit(''); |
|||
lenMin := MaxInt; |
|||
for i := 0 to ALength - 1 do |
|||
begin |
|||
// One string is empty |
|||
if self[i].IsEmpty then |
|||
exit(''); |
|||
self[i] := Reverse(self[i]); |
|||
// Get the minimum length of string |
|||
if lenMin > self[i].Length then |
|||
lenMin := self[i].Length; |
|||
end; |
|||
longest := -1; |
|||
repeat |
|||
inc(longest); |
|||
ref := self[0].Substring(0, longest + 1); |
|||
until not compare(ref, Self, longest + 1) or (longest >= lenMin); |
|||
Result := self[0].Substring(0, longest); |
|||
Result := reverse(Result); |
|||
end; |
|||
function TStringDynArrayHelper.Reverse(value: string): string; |
|||
var |
|||
ALength: Integer; |
|||
i: Integer; |
|||
c: Char; |
|||
begin |
|||
ALength := value.Length; |
|||
Result := value; |
|||
if ALength < 2 then |
|||
exit; |
|||
for i := 1 to ALength div 2 do |
|||
begin |
|||
c := Result[i]; |
|||
Result[i] := Result[ALength - i + 1]; |
|||
Result[ALength - i + 1] := c; |
|||
end; |
|||
end; |
|||
var |
|||
List: TStringDynArray; |
|||
begin |
|||
List := ['baabababc', 'baabc', 'bbbabc']; |
|||
Writeln('Input:'); |
|||
Writeln(List.Join(#10), #10); |
|||
Writeln('Longest common suffix = ', List.LongestSuffix); |
|||
Readln; |
|||
end. |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Input: |
|||
baabababc |
|||
baabc |
|||
bbbabc |
|||
Longest common suffix = abc |
|||
</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
Revision as of 21:55, 25 July 2020
- Task
The goal is to write a function to find the longest common suffix string amongst an array of strings.
Delphi
<lang Delphi> program Longest_common_suffix;
{$APPTYPE CONSOLE}
uses
System.SysUtils, Types;
type
TStringDynArrayHelper = record helper for TStringDynArray private class function Compare(const s: string; a: TStringDynArray; subSize: integer): Boolean; public function Reverse(value: string): string; function LongestSuffix: string; function Join(const sep: char): string; end;
{ TStringDynArrayHelper }
class function TStringDynArrayHelper.Compare(const s: string; a: TStringDynArray;
subSize: integer): Boolean;
var
i: Integer;
begin
for i := 0 to High(a) do if s <> a[i].Substring(0, subSize) then exit(False); Result := True;
end;
function TStringDynArrayHelper.Join(const sep: char): string; begin
Result := string.Join(sep, self);
end;
function TStringDynArrayHelper.LongestSuffix: string; var
ALength: Integer; i, lenMin, longest: Integer; ref: string;
begin
ALength := Length(self);
// Empty list if ALength = 0 then exit();
lenMin := MaxInt; for i := 0 to ALength - 1 do begin // One string is empty if self[i].IsEmpty then exit();
self[i] := Reverse(self[i]);
// Get the minimum length of string if lenMin > self[i].Length then lenMin := self[i].Length; end;
longest := -1; repeat inc(longest); ref := self[0].Substring(0, longest + 1); until not compare(ref, Self, longest + 1) or (longest >= lenMin);
Result := self[0].Substring(0, longest); Result := reverse(Result);
end;
function TStringDynArrayHelper.Reverse(value: string): string; var
ALength: Integer; i: Integer; c: Char;
begin
ALength := value.Length; Result := value;
if ALength < 2 then exit;
for i := 1 to ALength div 2 do begin c := Result[i]; Result[i] := Result[ALength - i + 1]; Result[ALength - i + 1] := c; end;
end;
var
List: TStringDynArray;
begin
List := ['baabababc', 'baabc', 'bbbabc'];
Writeln('Input:'); Writeln(List.Join(#10), #10); Writeln('Longest common suffix = ', List.LongestSuffix);
Readln;
end.
</lang>
- Output:
Input: baabababc baabc bbbabc Longest common suffix = abc
Factor
<lang factor>USING: accessors grouping kernel prettyprint sequences sequences.extras ;
! Like take-while, but for matrices and works from the rear.
- take-col-while-last ( ... matrix quot: ( ... col -- ... ? ) -- ... new-matrix )
[ [ <reversed> ] map flip ] dip take-while ; inline
- lcs ( seq -- lcs )
dup first swap [ all-equal? ] take-col-while-last to>> tail* ;
{ "baabababc" "baabc" "bbbabc" } lcs . { "baabababc" "baabc" "bbbazc" } lcs . { "" } lcs .</lang>
- Output:
"abc" "c" ""
Julia
<lang julia>function longestcommonsuffix(strings)
n, nmax = 0, minimum(length, strings) nmax == 0 && return "" while n <= nmax && all(s -> s[end-n] == strings[end][end-n], strings) n += 1 end return strings[1][end-n+1:end]
end
println(longestcommonsuffix(["baabababc","baabc","bbbabc"])) println(longestcommonsuffix(["baabababc","baabc","bbbazc"]))
println(longestcommonsuffix([""]))</lang>
- Output:
abc c
Perl
Based on Longest_common_prefix Perl entry. <lang perl>use strict; use warnings; use feature 'say';
sub lcs {
for (0..$#_) { $_[$_] = join , reverse split , $_[$_] } join , reverse split , (join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0];
}
for my $words (
[ <Sunday Monday Tuesday Wednesday Thursday Friday Saturday> ], [ <Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag> ], [ 2347, 9312347, 'acx5g2347', 12.02347 ], [ <longest common suffix> ], [ ('one, Hey!', 'three, Hey!', 'ale, Hey!', 'me, Hey!') ], [ 'suffix' ], [ ]) { say qq{'@$words' ==> '@{[lcs(@$words)]}';
}</lang>
- Output:
'Sunday Monday Tuesday Wednesday Thursday Friday Saturday' ==> 'day' 'Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag' ==> 'dag' '2347 9312347 acx5g2347 12.02347' ==> '2347' 'longest common suffix' ==> '' 'one, Hey! three, Hey! ale, Hey! me, Hey!' ==> 'e, Hey!' 'suffix' ==> 'suffix' '' ==> ''
Raku
<lang perl6>sub longest-common-suffix ( *@words ) {
return unless +@words; my $min = @words».chars.min; for 1 .. * { return @words[0].substr(* - $min) if $_ > $min; next if @words».substr(* - $_).Set == 1; return @words[0].substr(* - $_ + 1); }
}
say "{$_.raku} - LCS: >{longest-common-suffix $_}<" for
<Sunday Monday Tuesday Wednesday Thursday Friday Saturday>, <Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag>, ( 2347, 9312347, 'acx5g2347', 12.02347 ), <longest common suffix>, ('one, Hey!', 'three, Hey!', 'ale, Hey!', 'me, Hey!'), 'suffix', </lang>
- Output:
("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday") - LCS: >day< ("Sondag", "Maandag", "Dinsdag", "Woensdag", "Donderdag", "Vrydag", "Saterdag", "dag") - LCS: >dag< (2347, 9312347, "acx5g2347", 12.02347) - LCS: >2347< ("longest", "common", "suffix") - LCS: >< ("one, Hey!", "three, Hey!", "ale, Hey!", "me, Hey!") - LCS: >e, Hey!< "suffix" - LCS: >suffix< "" - LCS: ><
REXX
Essentially, this REXX version simply reversed the strings, and then finds the longest common prefix. <lang rexx>/*REXX program finds the longest common suffix contained in an array of strings. */ parse arg z; z= space(z) /*obtain optional arguments from the CL*/ if z==|z=="," then z='baabababc baabc bbbabc' /*Not specified? Then use the default.*/ z= space(z); #= words(z) /*#: the number of words in the list. */ say 'There are ' # " words in the list: " z zr= reverse(z) /*reverse Z, find longest common prefix*/ @= word(zr, 1); m= length(@) /*get 1st word in reversed string; len.*/
do j=2 to #; x= word(zr, j) /*obtain a word (string) from the list.*/ t= compare(@, x) /*compare to the "base" word/string. */ if t==1 then do; @=; leave /*A mismatch of strings? Then leave, */ end /*no sense in comparing anymore strings*/ if t==0 & @==x then t= length(@) + 1 /*Both strings equal? Compute length. */ if t>=m then iterate /*T ≥ M? Then it's not longest string.*/ m= t - 1; @= left(@, max(0, m) ) /*redefine max length & the base string*/ end /*j*/
say /*stick a fork in it, we're all done. */ if m==0 then say 'There is no common suffix.'
else say 'The longest common suffix is: ' right( word(z, 1), m)</lang>
- output when using the default input:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
Ring
<lang ring> load "stdlib.ring"
pre = ["baabababc","baabc","bbbabc"] len = len(pre) lenList = list(len) sub = list(len)
see "Input:" + nl see pre
for n = 1 to len
temp = pre[n] pre[n] = rever(temp)
next
for n = 1 to len
lenList[n] = len(pre[n])
next
lenList = sort(lenList) lenMax = lenList[1]
for m = 1 to lenMax
check = 0 sub1 = substr(pre[1],1,m) sub2 = substr(pre[2],1,m) sub3 = substr(pre[3],1,m) if sub1 = sub2 and sub2 = sub3 check = 1 ok if check = 1 longest = m ok
next
longPrefix = substr(pre[1],1,longest) longPrefix = rever(longPrefix)
see "Longest common suffix = " + longPrefix + nl
func rever(cstr)
cStr2 = "" for x = len(cStr) to 1 step -1 cStr2 = cStr2 + cStr[x] next return cStr2
</lang>
- Output:
Input: baabababc baabc bbbabc Longest common suffix = abc