### Re^3: Finding repeat sequences. (Results:Part 2. The winner)

by hdb (Monsignor)
 on Jun 19, 2013 at 19:07 UTC ( #1039830=note: print w/replies, xml ) Need Help??

Congrats to tobyink!

Thanks to your efforts, BrowserUK, I realized my mistakes in code and thinking. Should you ever get around to re-run your tests, here is a corrected version, don't know whether it is faster then tobyink's.

```hdb => sub {
my \$input = shift;
my \$length = length \$\$input;
my \$i = 0;
my \$possible;
my \$j;
while( 1 ) {
\$possible = substr \$\$input, 0, ++\$i;
\$possible = substr \$\$input, 0, \$i=\$j if( (\$j = index \$\$input, \$p
+ossible, \$i) > 0 );
return \$possible if substr( \$\$input, \$i ) eq substr(\$\$input, 0,
+\$length - \$i);
}
},

Replies are listed 'Best First'.
Re^4: Finding repeat sequences. (Results:Part 3. The **new** winner)
by BrowserUk (Pope) on Jun 19, 2013 at 19:46 UTC

Update: (I sent this to hdb as a /msg; and then decided it belongs in here): That is blinding! I've been looking for a solution that avoided being O(length string). Now I can stop looking. Thankyou!

Nice one++ Thank you :) (0.228s -v- 70.6s)

```Partisipants in performance tests: hdb tobyink
b:    4 in s:         7        hdb :: 0.000154 s
b:    4 in s:         7    tobyink :: 0.000169 s
b:    4 in s:        43        hdb :: 0.000098 s
b:    4 in s:        43    tobyink :: 0.000333 s
b:    4 in s:       402        hdb :: 0.000156 s
b:    4 in s:       402    tobyink :: 0.000190 s
b:    4 in s:      4003        hdb :: 0.000250 s
b:    4 in s:      4003    tobyink :: 0.000233 s
b:   26 in s:        44        hdb :: 0.000126 s
b:   26 in s:        44    tobyink :: 0.000104 s
b:   26 in s:       274        hdb :: 0.000040 s
b:   26 in s:       274    tobyink :: 0.000106 s
b:   26 in s:      2614        hdb :: 0.000031 s
b:   26 in s:      2614    tobyink :: 0.000086 s
b:   26 in s:     26008        hdb :: 0.000190 s
b:   26 in s:     26008    tobyink :: 0.000492 s
b: 6400 in s:      8044        hdb :: 0.000483 s
b: 6400 in s:      8044    tobyink :: 0.052703 s
b: 6400 in s:     69681        hdb :: 0.001241 s
b: 6400 in s:     69681    tobyink :: 0.240158 s
b: 6400 in s:    641930        hdb :: 0.017612 s
b: 6400 in s:    641930    tobyink :: 4.962130 s
b: 6400 in s:   6404352        hdb :: 0.208475 s
b: 6400 in s:   6404352    tobyink :: 65.351273 s
{
hdb => {
26 => {
1 => "0.000125885009765625",
10 => "4.00543212890625e-005",
100 => "3.09944152832031e-005",
1000 => "0.000190019607543945",
all => "0.000386953353881836",
},
4 => {
1 => "0.000154018402099609",
10 => "9.79900360107422e-005",
100 => "0.000156164169311523",
1000 => "0.000249862670898438",
all => "0.000658035278320313",
},
6400 => {
1 => "0.000483036041259766",
10 => "0.00124096870422363",
100 => "0.0176119804382324",
1000 => "0.208475112915039",
all => "0.227811098098755",
},
all => "0.228856086730957",
},
tobyink => {
26 => {
1 => "0.000103950500488281",
10 => "0.000106096267700195",
100 => "8.60691070556641e-005",
1000 => "0.000491857528686523",
all => "0.000787973403930664",
},
4 => {
1 => "0.000169038772583008",
10 => "0.000333070755004883",
100 => "0.000190019607543945",
1000 => "0.000233173370361328",
all => "0.000925302505493164",
},
6400 => {
1 => "0.0527029037475586",
10 => "0.240158081054688",
100 => "4.96213006973267",
1000 => "65.3512728214264",
all => "70.6062638759613",
},
all => "70.6079771518707",
},
}

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Here are the credits:

• tobyink for the basic algorithm and the boldness to step away from regexes.
• sundialsvc4 for the final check whether or not the solution is found,
• Eily to spot it in and extract it from sundialsvc4's writeup,
• BrowserUK pointing out that the first version didn't work,
• and to the Monastery for not expelling people loving to post code instead of lectures.

Create A New User
Node Status?
node history
Node Type: note [id://1039830]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (1)
As of 2018-05-28 00:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (198 votes). Check out past polls.

Notices?