2
$\begingroup$

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example

TYUFRIETEYM0SQZLHBCTN0W1KA9HELAT4LTQ14W7ZW484GSK1XTNOBJ2R6AMGW9KU36G7ITMPF315Y7ESYPR1XE2C1953J0DXUNBJLNTDG7IHS63854SGSS7YDEFJYSFP0DLL54GK6NUZ5UU5FRIETEYCPNGHIJOX23QOVSCBYHKE7HRIETEYV0H49I5SX9CW967CDGKX3TYCVNVBNCFGGDGDGDDFIIPGDSDVGDDSRGDGVCZAQRIOPKLMVFGCDGDTYGSDCBGDUSLVAQEFCGDGRIETEYDGDFG

In above character set there is two substring one is GD and other is RIETEY algorithm able to identify RIETEY because it is longest the substring, also pattern must occur at least twice to be considered a recurrence and patterns will not overlap.

I found a algorithm but it only work for less that 100,000 characters

any suggestion for this problem ?

$\endgroup$
8
  • 2
    $\begingroup$ Not everyone speaks Java, it is also hard to assume how your JVM implements collections. Could you possibly provide pseudocode? How do you define string? One character is one byte? What are possible characters in your string? What are probable lengths? What else have you tried besided given code? What do you expect? $\endgroup$
    – Evil
    Apr 6, 2016 at 17:47
  • 2
    $\begingroup$ It's not at all clear to me why that algorithm only works for inputs of length less than 100,000. $\endgroup$
    – David Richerby
    Apr 6, 2016 at 17:49
  • $\begingroup$ Let me guess - cannot allocate memory? $\endgroup$
    – Evil
    Apr 6, 2016 at 17:53
  • 1
    $\begingroup$ You need to get your requirements straight. "must be most repeated and it need to be longest substring" -- these two may be contradictory. $\endgroup$
    – Raphael ♦
    Apr 7, 2016 at 7:54
  • 1
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. Questions about code or debugging your code are off-topic here. $\endgroup$
    – D.W. ♦
    Apr 9, 2016 at 21:23

1 Answer 1

Reset to default
2
$\begingroup$

This problem is well-studied; it's aptly called longest repeated substring problem.

It can be solved in linear time by creating a suffix tree with Ukkonen's algorithm; the longest repeat corresponds to the labelling of the longest path from the root to an inner node which you find using breadth-first search.

This does not exclude overlapping substrings. Keep track of the smallest $m$ and largest $M$ starting index of sequences nodes represent while creating the tree; a node at depth $n$ (counted in symbols on the path) represents a non-overlapping repeat if and only if $M - m \geq n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.