Find the longest repeating string and the number of times it repeats in a given string

Question

For example, given string "abc fghi bc kl abcd lkm abcdefg", the function should return string "abcd" and the count of 2.

A O(n^2) solution seems easy but I am looking for a better solution.

Edited: If nothing better than O(n^2) is possible than which approach would be best performance wise.

Longest repeated substring problem: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem — sambowry, Jan 31 '10 at 14:44

score 9 · Accepted Answer · answered Jan 31 '10 at 14:48

9

You can solve this in linear time by building a suffix tree and taking a path from the root to the deepest internal node; this will give you the longest repeated string. Once you have that string, it's trivial to count the number of times it appears.

answered Jan 31 '10 at 14:48

jason

236,483
35
423
525

Mahmoud Al-Qudsi · Answer 2 · 2010-01-31T15:10:08.350

2

A state machine could probably give something better than big-O(N^2).

EDIT: The suffix tree suggested in the other answer is such an implementation of a state machine :)

edited Jan 31 '10 at 15:10

answered Jan 31 '10 at 14:42

Mahmoud Al-Qudsi

28,357
12
85
125

Find the longest repeating string and the number of times it repeats in a given string

2 Answers2

Linked