Longest common substring: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Fix 2 bugs: (1) 'aa', 'bb' gave 'a' not ''; (2) 'ab', 'bb' gave 'a'.) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 133:
Examples:<lang AutoHotkey>MsgBox % LCS("thisisatest", "testing123testing")</lang>
Outputs:<pre>test</pre>
=={{header|C}}==
Line 182 ⟶ 180:
{{out}}
<pre>test</pre>
=={{header|C sharp|C#}}==
Line 375 ⟶ 313:
string B = testing123testing
LCS = test
</pre>
=={{header|C++}}==
<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;
}
</lang>
{{out}}
<pre>
The longest common substring of thisisatest and testing123testing is:
"test" !
</pre>
Line 573 ⟶ 571:
<lang J> 'thisisatest' lcs 'testing123testing'
test</lang>
=={{header|Java}}==
<lang java>public class LongestCommonSubstring {
public static void main(String[] args) {
System.out.println(lcs("testing123testing", "thisisatest"));
}
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;
}
}</lang>
<pre>test</pre>
=={{header|JavaScript}}==
Line 691 ⟶ 718:
})();</lang>
{{Out}}
<pre>test</pre>
Line 851 ⟶ 849:
<code>StringTools:-CommonSubSequence()</code> returns the longest common subsequence() of two strings.
<lang Maple>StringTools:-LongestCommonSubString("thisisatest","testing123testing");</lang>
=={{header|Mathematica}}==
Line 956 ⟶ 953:
{{out}}
<pre>The longest common substring of <thisisatest> and <testing123testing> is test !</pre>
=={{header|Phix}}==
Line 1,257 ⟶ 1,224:
<pre>"test"</pre>
=={{header|Raku}}==
(formerly Perl 6)
<lang perl6>
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] ;
}
sub MAIN( Str $first , Str $second ) {
my $phrase = "The longest common substring of $first and $second is " ~
"{findLongestCommon( $first , $second ) } !" ;
$phrase.say ;
}</lang>
{{Out}}
<pre>The longest common substring of thisisatest and testing123testing is test !</pre>
=={{header|REXX}}==
Line 1,383 ⟶ 1,381:
}</lang>
=={{header|Sidef}}==
{{trans|Perl 6}}
| |||