4

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.

jason
  • 228,647
  • 33
  • 413
  • 517
AJ.
  • 2,536
  • 9
  • 44
  • 80

2 Answers2

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.

jason
  • 228,647
  • 33
  • 413
  • 517
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 :)

Mahmoud Al-Qudsi
  • 27,112
  • 12
  • 82
  • 123