Longest substrings without repeating characters: Difference between revisions
Longest substrings without repeating characters (view source)
Revision as of 10:48, 15 November 2021
, 2 years agoAdd Modula-2
(Add Factor) |
Not a robot (talk | contribs) (Add Modula-2) |
||
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]]
</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}}==
| |||