Longest substrings without repeating characters: Difference between revisions
Longest substrings without repeating characters (view source)
Revision as of 16:20, 3 May 2024
, 15 days agoAdded Easylang
(Added Easylang) |
|||
| (39 intermediate revisions by 22 users not shown) | |||
Line 3:
;Task:
Given a string, find the '''longest substring''' without any repeating characters.
{{Template:Strings}}
<br><br>
=={{header|11l}}==
{{trans|Python: Some optimisation}}
<syntaxhighlight lang="11l">F longest_substring2(s)
V max_subs = [s[0.<1]] * 0
V mx = 0
L(x) 0 .< s.len
L(y) x + 1 .. s.len
V sub = s[x .< y]
I y - x >= mx & sub.len == Set(Array(sub)).len
I y - x == mx & sub !C max_subs
max_subs.append(sub)
E
max_subs = [sub]
mx = y - x
R max_subs
L(s) [‘xyzyabcybdfd’, ‘xyzyab’, ‘zzzzz’, ‘a’, ‘’]
print(s‘ => ’longest_substring2(s))
V arr = [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]
print(arr‘ => ’longest_substring2(arr))</syntaxhighlight>
{{out}}
<pre>
xyzyabcybdfd => [zyabc, cybdf]
xyzyab => [zyab]
zzzzz => [z]
a => [a]
=> []
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">BYTE FUNC GetLength(CHAR ARRAY s BYTE start)
BYTE ARRAY tab(256)
BYTE i
CHAR c
Zero(tab,256)
i=start
WHILE i<=s(0)
DO
c=s(i)
tab(c)==+1
IF tab(c)>1 THEN
EXIT
FI
i==+1
OD
RETURN (i-start)
PROC LongestSubstrings(CHAR ARRAY s)
CHAR ARRAY tmp(256)
BYTE count,maxLen,i,len
IF s(0)=0 THEN
RETURN
FI
i=1 maxLen=0
FOR i=1 TO s(0)
DO
len=GetLength(s,i)
IF len>maxLen THEN
maxLen=len
FI
OD
count=0
FOR i=1 TO s(0)
DO
len=GetLength(s,i)
IF len=maxLen THEN
IF count>0 THEN
Print(", ")
FI
SCopyS(tmp,s,i,i+maxlen-1)
PrintF("""%S""",tmp)
count==+1
FI
OD
RETURN
PROC Test(CHAR ARRAY s)
PrintF("Input: ""%S""%E",s)
Print("Result: [")
LongestSubstrings(s)
PrintE("]") PutE()
RETURN
PROC Main()
Test("xyzyabcybdfd")
Test("xyzyab")
Test("zzzzz")
Test("a")
Test("thisisastringtest")
Test("")
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_substrings_without_repeating_characters.png Screenshot from Atari 8-bit computer]
<pre>
Input: "xyzyabcybdfd"
Result: ["zyabc", "cybdf"]
Input: "xyzyab"
Result: ["zyab"]
Input: "zzzzz"
Result: ["z", "z", "z", "z", "z"]
Input: "a"
Result: ["a"]
Input: "thisisastringtest"
Result: ["astring", "ringtes"]
Input: ""
Result: []
</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">with Ada.Text_IO;
procedure Longest_Substring is
function Longest (Item : String) return String is
Hist : array (Character) of Natural := (others => 0);
First : Natural := Item'First;
Last : Natural := Item'First - 1;
Longest_First : Natural := Item'First;
Longest_Last : Natural := Item'First - 1;
procedure Adjust is
begin
if Last - First > Longest_Last - Longest_First then
Longest_First := First;
Longest_Last := Last;
end if;
end Adjust;
begin
if Item = "" then
return Item;
end if;
for Index in Item'Range loop
Last := Index;
Hist (Item (Index)) := Hist (Item (Index)) + 1;
if Hist (Item (Index)) = 1 then
Adjust;
else
for A in First .. Index loop
if (for all E of Hist => E <= 1) then
First := A;
Adjust;
exit;
end if;
Hist (Item (A)) := Hist (Item (A)) - 1;
end loop;
end if;
end loop;
return Item (Longest_First .. Longest_Last);
end Longest;
procedure Test (Item : String) is
use Ada.Text_IO;
begin
Put ("original : '"); Put (Item); Put_Line ("'");
Put ("longest : '"); Put (Longest (Item)); Put_Line ("'");
end Test;
begin
Test ("");
Test ("a");
Test ("xyzyabcybdfd");
Test ("thisisastringtest");
Test ("zzzzz");
end Longest_Substring;</syntaxhighlight>
{{out}}
<pre>
original : ''
longest : ''
original : 'a'
longest : 'a'
original : 'xyzyabcybdfd'
longest : 'zyabc'
original : 'thisisastringtest'
longest : 'astring'
original : 'zzzzz'
longest : 'z'
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">lswrc←{
sfx ← ⌽∘,¨,\∘⌽
wrc ← ⊢(/⍨)⍳∘⍴(∧\=)⍳⍨
ls ← ⊢(/⍨)(⌈/=⊢)∘(≢¨)
ls wrc¨ sfx ⍵
}</syntaxhighlight>
{{out}}
<pre> lswrc¨ 'xyzyabcybdfd' 'xyzyab' 'zzzzz' 'a' ''
┌─────────────┬──────┬───────────┬───┬┐
│┌─────┬─────┐│┌────┐│┌─┬─┬─┬─┬─┐│┌─┐││
││cybdf│zyabc│││zyab│││z│z│z│z│z│││a│││
│└─────┴─────┘│└────┘│└─┴─┴─┴─┴─┘│└─┘││
└─────────────┴──────┴───────────┴───┴┘</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">unrepeatableSubstrings: function [s][
result: [["",0]]
if zero? s -> return []
if one? s -> return @[s]
loop 0..dec size s 'a [
if (a+1) =< dec size s [
loop a..dec size s 'b [
substr: to :string slice s a b
ss: size substr
if and? -> ss >= last maximum result 'x -> last x
-> substr = unique substr [
result: (select result 'x -> ss = last x) ++ @[@[substr, ss]]
]
]
]
]
result: unique map result 'x -> first x
return result
]
loop ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""] 'str ->
print [str "=> longest unrepeatable substring:" unrepeatableSubstrings str]</syntaxhighlight>
{{out}}
<pre>xyzyabcybdfd => longest unrepeatable substring: [zyabc cybdf]
xyzyab => longest unrepeatable substring: [zyab]
zzzzz => longest unrepeatable substring: [z]
a => longest unrepeatable substring: [a]
=> longest unrepeatable substring: []</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">LSWRC(str){
found := [], result := [], maxL := 0
if (StrLen(str) = 1)
result[str] := true
else while (StrLen(str) >= 2){
s := str
while StrLen(s) >= maxL{
if !(s ~= "(.).*\1"){
found[s] := true
maxL := maxL < StrLen(s) ? StrLen(s) : maxL
break
}
s := SubStr(s, 1, StrLen(s)-1) ; trim last chr
}
str := SubStr(str, 2) ; trim 1st chr and try again
}
maxL := 0
for str in found
maxL := maxL < StrLen(str) ? StrLen(str) : maxL
for str in found
if (StrLen(str) = maxL)
result[str] := true
return result
}</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">db =
(
xyzyabcybdfd
xyzyab
zzz
a
)
for i, line in StrSplit(db, "`n", "`r"){
result := "[", i := 0
for str in LSWRC(line)
result .= str ", "
output .= line "`t> " Trim(result, ", ") "]`n"
}
MsgBox % output
return</syntaxhighlight>
{{out}}
<pre>xyzyabcybdfd > [cybdf, zyabc]
xyzyab > [zyab]
zzz > [z]
a > [a]
</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
// Fills up 'v' with words where w%0 is the start and w%1 is the end
// of each longest substring
let lswrc(s, v) = valof
$( let seen = vec 255
let start = 1 and i = 1 and maxStart = 1 and maxEnd = 1 and n = 0
for i=0 to 255 do i!seen := false
while i <= s%0
$( test (s%i)!seen
while (s%i)!seen
$( (s%start)!seen := false
start := start + 1
$)
or
$( (s%i)!seen := true
if i - start >= maxEnd - maxStart
$( maxStart := start
maxEnd := i
while n>0 & (v+n-1)%1 - (v+n-1)%0 < i-start
do n := n-1
(v+n)%0 := start
(v+n)%1 := i
n := n+1
$)
i := i + 1
$)
$)
resultis n
$)
let substr(s, start, end, buf) = valof
$( buf%0 := end - start + 1
for i = start to end do
buf%(i-start+1) := s%i
resultis buf
$)
let example(s) be
$( let v = vec 32 and b = vec 32
let n = lswrc(s, v)
writef("Original string: '%s'*N", s)
writes("Longest substrings: ")
test n=0 do
writes("<empty>")
or for i = 0 to n-1 do
writef("'%s' ", substr(s, (v+i)%0, (v+i)%1, b))
wrch('*N')
$)
let start() be
$( example("xyzyabcybdfd")
example("xyzyab")
example("zzzzz")
example("a")
example("")
$)</syntaxhighlight>
{{out}}
<pre>Original string: 'xyzyabcybdfd'
Longest substrings: 'zyabc' 'cybdf'
Original string: 'xyzyab'
Longest substrings: 'zyab'
Original string: 'zzzzz'
Longest substrings: 'z' 'z' 'z' 'z' 'z'
Original string: 'a'
Longest substrings: 'a'
Original string: ''
Longest substrings: <empty></pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">LongUniq ← ⌈´⊸=∘(≠¨)⊸/ ∧`∘∊⊸/¨∘↓</syntaxhighlight>
Alternative:
<syntaxhighlight lang="bqn">LongUniq ← ⊢´∘⊔∘(≠¨)⊸⊏ ∊⊸⊐⟜0⊸↑¨∘↓</syntaxhighlight>
Test:
<syntaxhighlight lang="bqn">LongUniq¨ "a"‿""‿"zzz"‿"xyzyab"‿"xyzyabcybdfd"</syntaxhighlight>
{{out}}
<pre>┌─
· ⟨ "a" ⟩ ⟨ ⟨⟩ ⟩ ⟨ "z" "z" "z" ⟩ ⟨ "zyab" ⟩ ⟨ "zyabc" "cybdf" ⟩
┘</pre>
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
struct substr {
const char *start;
size_t length;
};
struct substr *lswrc(const char *str) {
size_t length = strlen(str);
struct substr *arr = malloc(sizeof(struct substr) * (length + 1));
if (!arr) return NULL;
size_t start=0, i=0, maxStart=0, maxEnd=0, n=0;
bool used[256] = {false};
for (i=0; i<length; i++) {
while (used[(unsigned char) str[i]])
used[(unsigned char) str[start++]] = false;
used[(unsigned char) str[i]] = true;
if (i-start >= maxEnd-maxStart) {
maxStart = start;
maxEnd = i;
size_t len = maxEnd - maxStart + 1;
while (n>0 && arr[n-1].length < len) n--;
arr[n].start = &str[start];
arr[n].length = len;
n++;
}
}
arr[n].start = NULL;
arr[n].length = 0;
return realloc(arr, sizeof(struct substr) * (n+1));
}
int main() {
char *examples[] = {"xyzyabcybdfd", "xyzyab", "zzzzz", "a", "", NULL};
for (size_t i=0; examples[i]; i++) {
printf("Original string: \"%s\"\n", examples[i]);
printf("Longest substrings: ");
struct substr *ls = lswrc(examples[i]);
for (size_t j=0; ls[j].start; j++)
printf("\"%.*s\" ", (int)ls[j].length, ls[j].start);
printf("\n");
free(ls);
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>Original string: "xyzyabcybdfd"
Longest substrings: "zyabc" "cybdf"
Original string: "xyzyab"
Longest substrings: "zyab"
Original string: "zzzzz"
Longest substrings: "z" "z" "z" "z" "z"
Original string: "a"
Longest substrings: "a"
Original string: ""
Longest substrings:</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include <fstream>
#include <set>
#include <sstream>
#include <string>
#include <vector>
std::vector<std::string> longest_substrings_without_repeats(const std::string& str) {
size_t max_length = 0;
std::vector<std::string> result;
size_t length = str.size();
for (size_t offset = 0; offset < length; ++offset) {
std::set<char> characters;
size_t len = 0;
for (; offset + len < length; ++len) {
if (characters.find(str[offset + len]) != characters.end())
break;
characters.insert(str[offset + len]);
}
if (len > max_length) {
result.clear();
max_length = len;
}
if (len == max_length)
result.push_back(str.substr(offset, max_length));
}
return result;
}
void print_strings(const std::vector<std::string>& strings) {
std::cout << "[";
for (size_t i = 0, n = strings.size(); i < n; ++i) {
if (i > 0)
std::cout << ", ";
std::cout << '\'' << strings[i] << '\'';
}
std::cout << "]";
}
void test1() {
for (std::string str : { "xyzyabcybdfd", "xyzyab", "zzzzz", "a", "thisisastringtest", "" }) {
std::cout << "Input: '" << str << "'\nResult: ";
print_strings(longest_substrings_without_repeats(str));
std::cout << "\n\n";
}
}
std::string slurp(std::istream& in) {
std::ostringstream out;
out << in.rdbuf();
return out.str();
}
void test2(const std::string& filename) {
std::ifstream in(filename);
if (!in) {
std::cerr << "Cannot open file '" << filename << "'.\n";
return;
}
std::cout << "Longest substring with no repeats found in '" << filename << "': ";
print_strings(longest_substrings_without_repeats(slurp(in)));
std::cout << "\n";
}
int main() {
test1();
test2("unixdict.txt");
}</syntaxhighlight>
{{out}}
<pre>
Input: 'xyzyabcybdfd'
Result: ['zyabc', 'cybdf']
Input: 'xyzyab'
Result: ['zyab']
Input: 'zzzzz'
Result: ['z', 'z', 'z', 'z', 'z']
Input: 'a'
Result: ['a']
Input: 'thisisastringtest'
Result: ['astring', 'ringtes']
Input: ''
Result: []
Longest substring with no repeats found in 'unixdict.txt': ['mbowel
disgrunt']
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
func$[] longstr s$ .
subr maxtest
if len sub$ >= max
if len sub$ > max
max = len sub$
max$[] = [ ]
.
max$[] &= sub$
.
.
s$[] = strchars s$
len empty[] 255
len pos[] 255
pos = 1
while pos <= len s$[]
c = strcode s$[pos]
if pos[c] > 0
maxtest
pos = pos[c] + 1
pos[] = empty[]
sub$ = ""
c = strcode s$[pos]
.
pos[c] = pos
sub$ &= strchar c
pos += 1
.
maxtest
return max$[]
.
for s$ in [ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "thisisastringtest" "" ]
print longstr s$
.
</syntaxhighlight>
{{out}}
<pre>
[ "zyabc" "cybdf" ]
[ "zyab" ]
[ "z" "z" "z" "z" "z" ]
[ "a" ]
[ "astring" "ringtes" ]
[ "" ]
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<syntaxhighlight lang="factor">USING: formatting grouping io kernel math sequences sets ;
: unique-substrings ( seq n -- newseq )
tuck <clumps> [ cardinality = ] with filter ;
: longest-unique-substring ( seq -- newseq )
dup length { } [ 2dup empty? swap 0 > and ]
[ drop 2dup unique-substrings [ 1 - ] dip ] while
2nip [ "" like ] map members ;
: test ( seq -- )
dup longest-unique-substring "%u -> %u\n" printf ;
"Longest substrings without repeating characters:" print
{ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "" } [ test ] each</syntaxhighlight>
{{out}}
<pre>
Longest substrings without repeating characters:
"xyzyabcybdfd" -> { "zyabc" "cybdf" }
"xyzyab" -> { "zyab" }
"zzzzz" -> { "z" }
"a" -> { "a" }
"" -> { }
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">dim as string example = "antidisestablishmentarianism is a long word and so is flibbertigibbet."
function nrls( t as string ) as string
dim as integer best=0, best_length=-100, i=1, j, k, curr_length
dim as string c
for i = 1 to len(t)+1
curr_length = 0
for j = i+1 to len(t)+1
curr_length += 1
c = mid(t, j, 1)
for k = i to j - 1
if c = mid(t, k, 1) then goto nexti
next k
next j
nexti:
if curr_length > best_length then
best_length = curr_length
best = i
end if
next i
return mid(t, best, best_length)
end function
print ">";nrls(example);"<"
print ">";nrls("My spoon is too big.");"<"
print ">";nrls("Rosetta Code.");"<"
print ">";nrls("AAAAA");"<"
print ">";nrls("abcdefghijklmnopqrstuvwxyz");"<"
print ">";nrls("aaa aeiou uuu");"<"
</syntaxhighlight>
{{out}}<pre>
>blishmentar<
>My spo<
>ta Code.<
>A<
>abcdefghijklmnopqrstuvwxyz<
> aeiou<
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="future basic">
local fn substrings( t as CFStringRef )
int beg, c, f, rpt, max = 0
for beg = 0 to len(t) - 1
rpt = instr( beg+1, t, mid(t, beg, 1), NSCaseInsensitiveSearch )
if rpt < 0 then rpt = len(t)
c = beg + 1
while c < rpt
f = instr(c + 1, t, mid(t, c, 1), NSCaseInsensitiveSearch)
if f < 0 then f = len(t) else if f < rpt then rpt = f
c++
wend
if rpt - beg < max then continue
if rpt - beg > max then max = rpt - beg : mda_clear
mda_add(0) = mid(t, beg, max)
next
print @"\n The string: \"";t;@"\"\n Substring/s: ";
for c = 0 to mda_count(0) -1
print @"\"";mda(c);@"\" ";
next
print
end fn
window 1, @"Longest Substring/s Without Repeated Letters"
fn substrings(@"xyzyabcybdfd")
fn substrings(@"thisisastringtest")
fn substrings(@"My spoon is too big.")
fn substrings(@"Rosetta Code")
fn substrings(@"AaAaA")
fn substrings(@"abcdefghijklmnopqrstuvwxyz")
fn substrings(@"aaa aeiou uuu")
fn substrings(@"abcdABCD")
handleevents
</syntaxhighlight>
{{out}}
[[File:Longest Substrings without Repeated Letters.png]]
=={{header|Go}}==
{{trans|Wren}}
<syntaxhighlight lang="go">package main
import "fmt"
func substrings(s string) []string {
n := len(s)
if n == 0 {
return []string{""}
}
var ss []string
for i := 0; i < n; i++ {
for le := 1; le <= n-i; le++ {
ss = append(ss, s[i:i+le])
}
}
return ss
}
func distinctRunes(chars []rune) []rune {
m := make(map[rune]bool)
for _, char := range chars {
m[char] = true
}
var l []rune
for k := range m {
l = append(l, k)
}
return l
}
func distinctStrings(strings []string) []string {
m := make(map[string]bool)
for _, str := range strings {
m[str] = true
}
var l []string
for k := range m {
l = append(l, k)
}
return l
}
func main() {
fmt.Println("The longest substring(s) of the following without repeating characters are:\n")
strs := []string{"xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""}
for _, s := range strs {
var longest []string
longestLen := 0
for _, ss := range substrings(s) {
if len(distinctRunes([]rune(ss))) == len(ss) {
if len(ss) >= longestLen {
if len(ss) > longestLen {
longest = longest[:0]
longestLen = len(ss)
}
longest = append(longest, ss)
}
}
}
longest = distinctStrings(longest)
fmt.Printf("String = '%s'\n", s)
fmt.Println(longest)
fmt.Printf("Length = %d\n\n", len(longest[0]))
}
}</syntaxhighlight>
{{out}}
<pre>
The longest substring(s) of the following without repeating characters are:
String = 'xyzyabcybdfd'
[zyabc cybdf]
Length = 5
String = 'xyzyab'
[zyab]
Length = 4
String = 'zzzzz'
[z]
Length = 1
String = 'a'
[a]
Length = 1
String = ''
[]
Length = 0
</pre>
=={{header|J}}==
Implementation:<syntaxhighlight lang="j">longnorep=: {{
c=. #y
while. ss=. c ]\ y do.
cnt=. #@~."1 ss
if. c e. cnt do. ~.ss#~ c=cnt return. end.
c=. c-1
end.
}}</syntaxhighlight>
Examples:
<syntaxhighlight lang="j"> longnorep 'xyzyabcybdfd'
zyabc
cybdf
longnorep 'xyzyab'
zyab
longnorep 'zzzzz'
z
longnorep ''
longnorep 'astring'
astring
longnorep 'thisisastringtest'
astring
ringtes
longnorep 'Thequickbrownfoxjumpsoverthelazydog'
Thequickbrownf</syntaxhighlight>
This also works on sequences of numbers (though the character representation of the sequences of numbers may contain repeated characters, the represented numbers will not contain repetitions):
<syntaxhighlight lang="j"> longnorep 1 2 3 4 1 2 5 6 1 7 8 1 0
3 4 1 2 5 6
2 5 6 1 7 8</syntaxhighlight>
=={{header|jq}}==
'''Adapted from [[#Julia|Julia]]'''
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq"># Use a dictionary for speed in case of very long strings
def alluniquehead:
length as $n
| if $n <= 1 then .
else . as $in
| {ix: -1}
| until(.i or (.ix == $n);
.ix += 1
| $in[.ix:.ix+1] as $x
| if .dict[$x] then .i = .ix
else .dict[$x] = true
end )
| $in[: .ix]
end ;
def maximal_substring_with_distinct_characters:
. as $in
| length as $n
| {i: -1}
| until( .i == $n or .stop;
.i += 1
| if .max and .max > $n - .i then .stop = true
else ($in[.i:] | alluniquehead) as $head
| if ($head|length) > .max
then .ans = $head
| .max = ($head|length)
else .
end
end)
| .ans;
</syntaxhighlight>
'''Test Cases'''
<syntaxhighlight lang="jq">"xyzyabcybdfd",
"xyzyab",
"zzzzz",
"a", "α⊆϶α϶",
""
| "\"\(.)\" => \"\(maximal_substring_with_distinct_characters)\""
</syntaxhighlight>
{{out}}
<pre>
"xyzyabcybdfd" => "zyabc"
"xyzyab" => "zyab"
"zzzzz" => "z"
"a" => "a"
"α⊆϶α϶" => "α⊆϶"
"" => ""
</pre>
=={{header|Julia}}==
Works on any array, treating a character string as a character array.
<
len = length(arr)
if len > 1
Line 32 ⟶ 904:
println("\"$s\" => ", uarray)
end
</
<pre>
"xyzyabcybdfd" => ["zyabc", "cybdf"]
Line 41 ⟶ 913:
"" => Char[]
"[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]" => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [ Stdout (show test ++ " -> " ++ show (lswrc test) ++ "\n")
| test <- tests]
tests :: [[char]]
tests = ["xyzyabcybdfd", "xyzyab", "zzz", "a"]
lswrc :: [*]->[[*]]
lswrc s = nub [s' | s'<-noreps; #s' = maxlen]
where maxlen = max (map (#) noreps)
noreps = [norep (drop n s) | n<-[0..#s-1]]
norep = reverse . norep' []
norep' mem [] = mem
norep' mem (a:as) = mem, if a $in mem
= norep' (a:mem) as, otherwise
in :: *->[*]->bool
in item [] = False
in item (a:as) = a = item \/ item $in as
nub :: [*]->[*]
nub = reverse . nub' []
where nub' mem [] = mem
nub' mem (a:as) = nub' mem as, if a $in mem
= nub' (a:mem) as, otherwise</syntaxhighlight>
{{out}}
<pre>"xyzyabcybdfd" -> ["zyabc","cybdf"]
"xyzyab" -> ["zyab"]
"zzz" -> ["z"]
"a" -> ["a"]</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE LSWRC;
FROM InOut IMPORT WriteString, WriteLn;
FROM Strings IMPORT Length, Copy;
TYPE Range =
RECORD
start, length: CARDINAL;
END;
(* Returns start and length of every longest substring *)
PROCEDURE lswrc(in: ARRAY OF CHAR; VAR out: ARRAY OF Range): CARDINAL;
VAR i, num, start, strlen, len, maxStart, maxEnd: CARDINAL;
used: ARRAY [0..255] OF BOOLEAN;
BEGIN
FOR i := 0 TO 255 DO used[i] := FALSE; END;
strlen := Length(in);
start := 0;
maxStart := 0;
maxEnd := 0;
i := 0;
num := 0;
WHILE i < strlen DO
IF NOT used[ORD(in[i])] THEN
used[ORD(in[i])] := TRUE;
IF (i - start) >= (maxEnd - maxStart) THEN
maxStart := start;
maxEnd := i;
len := (maxEnd - maxStart + 1);
WHILE (num > 0) AND (out[num-1].length < len) DO
DEC(num);
END;
out[num].start := start;
out[num].length := len;
INC(num);
END;
INC(i);
ELSE
WHILE used[ORD(in[i])] DO
used[ORD(in[start])] := FALSE;
INC(start);
END;
END;
END;
RETURN num;
END lswrc;
PROCEDURE Example(s: ARRAY OF CHAR);
VAR buf: ARRAY [0..127] OF CHAR;
ranges: ARRAY [0..127] OF Range;
i, n: CARDINAL;
BEGIN
WriteString("Original string: ");
WriteString(s);
WriteLn();
n := lswrc(s, ranges);
WriteString("Longest substrings: ");
IF n = 0 THEN
WriteString("<empty>");
ELSE
FOR i := 0 TO n-1 DO
Copy(s, ranges[i].start, ranges[i].length, buf);
buf[ranges[i].length] := CHR(0);
WriteString(buf);
WriteString(" ");
END;
END;
WriteLn();
END Example;
BEGIN
Example("xyzyabcybdfd");
Example("xyzyab");
Example("zzzzz");
Example("a");
Example("");
END LSWRC.</syntaxhighlight>
{{out}}
<pre>Original string: xyzyabcybdfd
Longest substrings: zyabc cybdf
Original string: xyzyab
Longest substrings: zyab
Original string: zzzzz
Longest substrings: z z z z z
Original string: a
Longest substrings: a
Original string:
Longest substrings: <empty></pre>
=={{header|Nim}}==
This version converts strings to sequences of runes.
<syntaxhighlight lang="nim">import sequtils, strutils, unicode
type Runes = seq[Rune]
func longestSubstrings(str: string): seq[string] =
var runes = str.toRunes
var current: Runes
var res: seq[Runes] # Result as a list of Runes.
var maxlen = 0
for c in runes:
let idx = current.find(c)
if idx >= 0:
if current.len > maxlen:
res = @[current]
maxlen = current.len
elif current.len == maxlen and current notin res:
res.add current
current.delete(0, idx)
current.add c
# Process the last current string.
if current.len > maxlen: res = @[current]
elif current.len == maxlen and current notin res: res.add current
result = res.mapIt($it)
for str in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", ""]:
echo '"', str, '"', " → ", longestSubstrings(str)
echo "\nLongest substrings in concatenated list of words from “unixdict.txt”: ",
longestSubstrings(toSeq("unixdict.txt".lines).join())</syntaxhighlight>
{{out}}
<pre>"xyzyabcybdfd" → @["zyabc", "cybdf"]
"xyzyab" → @["zyab"]
"zzzzz" → @["z"]
"a" → @["a"]
"α⊆϶α϶" → @["α⊆϶", "⊆϶α"]
"" → @[""]
Longest substrings in concatenated list of words from “unixdict.txt”: @["mboweldisgrunt"]</pre>
=={{header|Perl}}==
Gets the same answer that raku does when run against unixdict.txt
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # Longest_substrings_without_repeating_characters
use warnings;
for my $string ( qw( xyzyabcybdfd xyzyab zzzzz a thisisastringtest ) )
{
local $_ = $string;
my @sub;
length $+ >= $#sub and ++$sub[length $+]{$+} while s/.*(.)(.*\K\1.*)|(.+)//s;
printf "%20s -> %s\n", $string, join ' ', sort keys %{ pop @sub };
}</syntaxhighlight>
{{out}}
<pre>
xyzyabcybdfd -> cybdf zyabc
xyzyab -> zyab
zzzzz -> z
a -> a
thisisastringtest -> astring ringtes
</pre>
=={{header|Phix}}==
Single pass, maintains a
If the current character
Note that having moved start along we certainly won't be any longer than but may still be ''equal'' to maxlen.<br>
Should be exponentially faster than collecting all possible substrings and eliminating those with duplicate characters or too short.<br>
It will however collect duplicates (when long enough) before weeding them out at the end.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- s can be a normal 8-bit acsii/ansi string or a
-- 32-bit unicode sequence from eg utf8_to_utf32().
--
-- chop up
-- s must not contain any 0 or non-
--</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #
<span style="color: #004080;">integer</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</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;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (deliberate typecheck)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (
<span style="color: #
<span style="color: #
<span style="color: #008080;">if</span> <span style="color: #000000;">fi</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">start</span> <span style="color: #008080;">then</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #
<span style="color: #004080;">integer</span> <span style="color: #000000;">newlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">start</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span>
<span style="color: #
<span style="color: #000000;">
<span style="color: #
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">start</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 97 ⟶ 1,152:
<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"a"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 110 ⟶ 1,165:
=={{header|Python}}==
The following algorithm works but is not terribly efficient for long strings.
<
substr = [s[x:y] for x in range(len(s)) for y in range(x+1, len(s) + 1)]
no_reps = []
Line 123 ⟶ 1,178:
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "",
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]:
print(f"{s} => {longest_substring(s)}")</
{{out}}
Line 136 ⟶ 1,191:
===Python: Some optimisation===
The following algorithm only accrues the longest so far.
<
max_subs, mx = [], 0
for x in range(len(s)):
Line 146 ⟶ 1,201:
else:
max_subs, mx = [sub], y - x
return max_subs</
{{out}}
Line 157 ⟶ 1,212:
Not going to bother handling arrays since an array is not a string, and the task description '''specifically''' says 'Given a string'.
<syntaxhighlight lang="raku"
sub longest ($string) {
Line 183 ⟶ 1,238:
# check a file
slurp 'unixdict.txt';</
{{out}}
<pre>Original string: xyzyabcybdfd
Line 225 ⟶ 1,280:
=={{header|REXX}}==
<
parse arg $ /*obtain optional argument from the CL.*/
if $=='' | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/
Line 234 ⟶ 1,289:
x= /*X: the substring, less the 1st char*/
do k=j+1 to L; x= x || substr($, k, 1) /*search for the max length substrings.*/
if \
_= length(x); if _<maxL then iterate /*is length less then the current max? */
@._= @._ x; maxL= _ /*add this substring to the max list. */
Line 247 ⟶ 1,302:
OKx: procedure; parse arg y; do r=1 for length(y)-1 /*look for duplicate chars.*/
if pos(substr(y, r, 1), y, r+1)>0 then return 0
end /*r*/; return 1</
{{out|output|text= when using the default input:}}
<pre>
Line 254 ⟶ 1,309:
=={{header|Ring}}==
<
see "working..." + nl
see "Longest substrings without repeating characters are:" + nl
Line 305 ⟶ 1,360:
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 315 ⟶ 1,370:
done...
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
function nrls(byval s1)
dim i,x
if len(s1)<2 then nlrs=s :exit function
s=lcase(replace(s1," ",""))
redim a(127)
dim ls:ls=len(s)
start=1
so=""
ml=1
a(asc(left(s,1)))=1
for i=2 to ls+1
if i>ls then
rep=true
else
x=asc(mid(s,i,1))
rep=a(x)<>0
end if
if a(x)<>0 then
if (i-start)>ml then
so= mid(s,start,i-start)
ml=(i-start)
elseif (i-start)=ml then
so=so & " " & mid(s,start,i-start)
end if
xx=a(x)
for j= 96 to 122:
if a(j)<=x then a(j)=0
next
start=xx+1
end if
a(x)=i
next
nrls=trim(so)
erase a
end function
sub test (f)
wscript.stdout.writeline "Original: "&f
wscript.stdout.writeline "Substrings: "&nrls(f)&vbcrlf
end sub
test "dabale arroz a la zorra el abad"
test "The quick brown fox jumps over the lazy dog"
test "ae"
test "aa"
test "abdefghij"
</syntaxhighlight>
{{out}}
<pre>
Original: dabale arroz a la zorra el abad
Substrings: rozal lazor
Original: The quick brown fox jumps over the lazy dog
Substrings: thequickbrownf
Original: ae
Substrings: ae
Original: aa
Substrings: a a
Original: abdefghij
Substrings: abdefghij
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">fn substrings(s string) []string {
n := s.len
if n == 0 {
return [""]
}
mut ss := []string{}
for i in 0..n {
for le := 1; le <= n-i; le++ {
ss << s[i..i+le]
}
}
return ss
}
fn distinct_runes(chars []rune) []rune {
mut m := map[rune]bool{}
for c in chars {
m[c] = true
}
mut l := []rune{}
for k,_ in m {
l << k
}
return l
}
fn distinct_strings(strings []string) []string {
mut m := map[string]bool{}
for str in strings {
m[str] = true
}
mut l := []string{}
for k,_ in m {
l << k
}
return l
}
fn main() {
println("The longest substring(s) of the following without repeating characters are:\n")
strs := ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""]
for s in strs {
mut longest := []string{}
mut longest_len := 0
for ss in substrings(s) {
if distinct_runes(ss.runes()).len == ss.len {
if ss.len >= longest_len {
if ss.len > longest_len {
longest = longest[..0]
longest_len = ss.len
}
longest << ss
}
}
}
longest = distinct_strings(longest)
println("String = '$s'")
println(longest)
println("Length = ${longest[0].len}\n")
}
}</syntaxhighlight>
{{out}}
<pre>Same as Wren entry</pre>
=={{header|Wren}}==
{{libheader|Wren-seq}}
<
var substrings = Fn.new { |s|
Line 331 ⟶ 1,520:
System.print("The longest substring(s) of the following without repeating characters are:\n")
var strs = ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""
for (s in strs) {
var longest = []
Line 342 ⟶ 1,531:
longestLen = ss.count
}
longest.add(ss
}
}
Line 351 ⟶ 1,540:
System.print(longest)
System.print("Length = %(longest[0].count)\n")
}</
{{out}}
| |||