I have a program that I wrote that searches through a string of digits and prints out all the matches of substrings that are repeated.

String:

2305843009213693951

Results:

length: 1 digits: 0 quantity: 3
length: 1 digits: 1 quantity: 2
length: 1 digits: 2 quantity: 2
length: 1 digits: 3 quantity: 4
length: 1 digits: 5 quantity: 2
length: 1 digits: 9 quantity: 3
length: 2 digits: 30 quantity: 2
[download]

The program:

#!/usr/bin/perl -w
use strict;
my $line;
while ( defined ( $line = <> ) ) {
        chomp $line;
        for my $a ( 1 .. length ( $line ) ) {
                for my $b ( 1 .. ( length ( $line ) + 1 - $a ) ) {
                        my $out = substr ( $line, $a - 1, $b );
                        my $count = () = $line =~ /$out/g;
                        print "length: $b digits: $out quantity: $coun
+t\n" if $count > 1;
                }
        }
}
[download]

How I run it:

$ ./test < textfile | sort | uniq

The input string is formatted to be only the digits. I stripped all other characters except the trailing newline beforehand. I don't have any error checking for the input in place yet.

My thought process here is to generate every possible substring and then check each of these against the string and count the results. If the result is greater than 1 then I print it out. Since any result greater than 1 will have multiple answers, I sort the results and then run uniq on them. This also sorts the results so the largest ones are listed last.

Now, the program works, but as the string gets longer it gets much slower. I have gotten up to a 6,500 digit string (M25) which took about 30 minutes on a 2.8GHz P4.

My goal is to test a 9 million digit string (M43). I assume I need a more intelligent way to code this. The brute force approach isn't going to work.

Here is a web page of the strings I am working with:

http://www.mersennewiki.org/index.php/Mersenne_primes

The files I am working with are the ones in the third column.

Right now those files are split across multiple lines. I manually fix them (cat file | tr -d '\n' | sed 's/$/\n/' > a.a ; mv a.a file) but it would be nice to have this done by the program.

Warning: I know my Perl skills are weak, so please take it easy on me with regard to my coding style. I am interested in learning but I need it in baby steps. :)

Finally, the reason I started this programming exercise:

http://www.mersenneforum.org/showthread.php?t=5414

(I am "Xyzzy" on that forum.)

Again, I am very new to programming so I usually have do "reverse engineer" code snippets to a flow chart before I can really understand them.

I assume my problem here (Other than the ugly code) is the fact that the number of possible substrings is growing exponentially.

Thanks for any help!

PS - I also don't understand the () in: my $count = () = $line =~ /$out/g;

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.