Longest substrings without repeating characters: Difference between revisions
Content added Content deleted
(Add Factor) |
Not a robot (talk | contribs) (Add Modula-2) |
||
Line 392: | Line 392: | ||
"[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]] |
"[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> |
</pre> |
||
=={{header|Modula-2}}== |
|||
<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.</lang> |
|||
{{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}}== |
=={{header|Nim}}== |