Given a string find the substring which appears most often

Question

Write a complete program (not just a function) which using stdin takes in a string of arbitrary length (assume string-length at least one) composed only of digits 0-9 and outputs using stdout the substring which appears most often in the input string. The input string can be any length and the substring can be maximum half the length of the input string because it must appear at least twice non-overlapped to be printed.

We following the following hierarchy selecting the substring to be printed.

1. First priority, the longest substring
2. Second priority, if we have multiple substrings of the same length, we pick the one appearing the most often.
3. Third priority, if multiple substrings of the same size appear the same number of times, pick the one which appears first scanning from the left.

Here are some test cases followed by the rules and some explanation.

./myprogram 123456
No substrings repeat.

The substring must appear more than once. If no substrings repeat the the output must exactly be the string "No substrings repeat." complete with the capitalization and the period.

./myprogram 12121
12

The sub-strings must not overlap. So in this case the largest repeating substring is 12 instead of 121.

./myprogram 99999999
9999

We want the largest substring which appears at least twice. Here 9, 99, 999, and 9999 all appears at least twice. But we want the largest substring which appears at least twice.

./myprogram 321321788788788
788

321, 788, 887, and 878 each appear multiple times so we pick 788 which appears the most often.

./myprogram 12121
12

12 and 21 both appear twice so we pick 12 which appears first from the left.

./myprogram 12012112299999999
9999

The string 12 occurs first and appears thrice but 9999 is longer and appears only twice so we pick 9999 because it has the highest priority.

./myprogram 56698853211564788954126162561664412355899990001212345
412

No substrings of length more than three repeat. 412, 616, and 123 each appear twice. 412 occurs first and is thus printed.

I think I have taken care of all the cases. True code-golf. The shortest code in any language wins. In the case of ties, I pick the one with the highest upvotes after waiting at least for two weeks and probably longer. So the community please feel free to upvote any solutions you like. The cleverness/beauty of the code matters much more than who posts first.

Happy coding!

Answer 1

ruby, 104 characters

r=gets.size.downto 1
r.find{|l|r.find{|c|$><<$1 if/(.{#{l}})(.*\1){#{c}}/}}||$><<"No substrings repeat."

Uses my favourite, nested finds. Also, good old magic variables and other perlisms.

Answer 2

Perl, 99 (+1) bytes

$_=$;{(sort%;)[m{(.+).*\1(?{$;{$;x$+=~y///c.1x@{[/$+/g]}.2x$+[1]}=$+})^}]}
||"No substrings repeat."

Requires a -p command line switch.

For each repeated substring a hash entry is created, such that the largest substring, repeated the most times, with the earliest position is guaranteed to be the smallest key in the hash. The hash is then sorted, and the corresponding value for the smallest key is output.

Sample Usage:

$ echo 123456 | perl -p repeated-substring.pl
No substrings repeat.

$ echo 12121 | perl -p repeated-substring.pl
12

$ echo 99999999 | perl -p repeated-substring.pl
9999

$ echo 321321788788788 | perl -p repeated-substring.pl
788

$ echo 12012112299999999 | perl -p repeated-substring.pl
9999

$ echo 56698853211564788954126162561664412355899990001212345 | perl -p repeated-substring.pl
412

Answer 3

GolfScript, 74 characters

"No substrings repeat."\:i,,{){i@><}+i,,%.{i\/,}%$-1=.2>*{i@/,=}+,0=}/]-1=

Brute force GolfScript approach (which would have been much shorter if $ would be stable). Note that the input must include the newline in order to give correct results.

Answer 4

Ruby, 108+1=109

$_=$_.scan(/(.+)(?=.*\1)/).map(&:first).max_by{|s|[s.size,$_.scan(s).size,-~/#{s}/]}||'No substrings repeat.'

Usage:

echo 56698853211564788954126162561664412355899990001212345 | ruby -p repeats_most_often.rb

I could save a few chars if I assumed Ruby's sort was stable, but it's not always. Also in older versions of Ruby I could replace the $_.scan with scan.

Answer 5

C#, 120 chars

Regex.Matches("(.{2,}).*\1",input).Select(n=>n.ToString()).OrderBy(n=>n.Length).LastOrDefault()??"No substrings repeat."

With boilerplate, 171

class A{int Main(string[] a){Console.WriteLine(Regex.Matches("(.{2,}).*\1", a[0]).Select(n=>n.ToString()).OrderBy(n=>n.Length).LastOrDefault()??"No substrings repeat.");}}