Rosetta Code

Longest substrings without repeating characters: Difference between revisions

Page Discussion

Longest substrings without repeating characters (view source)

Revision as of 17:26, 4 August 2021

427 bytes removed ,  2 years ago
→‎{{header|Phix}}: simplified: use found to hold indices instead of bools.
(Added Go)
(→‎{{header|Phix}}: simplified: use found to hold indices instead of bools.)
Line 301:
 
=={{header|Phix}}==
Single pass, maintains a tablestart of seen charactersposition and a starttable positionof seen character positions.<br>
If the current character occurshas inoccurred after start..i, wemove trimthat left until clearedalong, otherwise/then we add any longer/equal lenlength start..i to the result set.<br>
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 then eliminating those with duplicate characters or too short.<br>
It will however collect duplicates (when long enough) before weeding them out at the end.
<!--<lang Phix>(phixonline)-->
Line 310 ⟶ 311:
<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().
-- itIt will not complain if given utf-8, but it may
-- chop up multi-bytemultibyte characters inappropriately.
-- s must not contain any 0 or non-integer elementsintegers.
--</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: #004600000000;">false0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (for ansi, position)</span>
<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;">-- (formust be unicode then)</span>
<span style="color: #0000007060A8;">foundassert</span> <span style="color: #0000FF;">&=(</span> <span style="color: #7060A8000000;">repeatsi</span><span style="color: #0000FF;">(<=</span><span style="color: #004600000000;">false#10FFFF</span><span style="color: #0000FF;">,)</span><span style="color: #000000;">si</span><span style="color: #0000FF000080;">font-</span><span style="color: #7060A8italic;">length</span><span-- style="color: #0000FF;">(</span><spanlimit style="color:size #000000;">found</span><spanto style="color:valid #0000FF;">)chars)</span>
<span style="color: #008080000000;">elsiffound</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found0</span><span style="color: #0000FF;">[,</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]-</span><span style="color: #7060A8;">length</span><span style="color: #0080800000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">then))</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">doelse</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ssfi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sfound</span><span style="color: #0000FF;">[</span><span style="color: #000000;">startsi</span><span style="color: #0000FF;">]</span>
<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> <span style="color: #000000;">fi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <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;">ss</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ss</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- aside: we will not have found anything
-- longer, but may have trimmed 1 added 1
-- and therefore still be === maxlen.</span>
<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: #004600000000;">truei</span>
<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: #000000008080;">resif</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxlen</span> <span style="color: #0000FF008080;">{}then</span>
<span style="color: #000000;">maxlenres</span> <span style="color: #0000FF;">=</span> <span style="color: #0000000000FF;">newlen{}</span>
<span style="color: #008080000000;">endmaxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #008080000000;">ifnewlen</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF008080;">=</span><span style="color: #000000;">maxlenend</span> <span style="color: #008080;">thenif</span>
<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>
Petelomax
7,803

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/312451"