Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigInteger;
- import java.util.HashMap;
- import java.util.Map;
- import java.util.Random;
- public class LongestRepeatedNonOverlappingSubstring {
- public static void main(String[] args) {
- String text = "abcabca";
- String repeated = getLongestRepeatedNonOverlappingSubstring(text);
- System.out.println(repeated);
- }
- public static String getLongestRepeatedNonOverlappingSubstring(String text) {
- if (text == null) {
- throw new IllegalArgumentException("Must pass in a non-null string!");
- }
- int n = text.length();
- int low = 1;
- int high = n;
- String best = "";
- while (low <= high) {
- int mid = low + (high - low) / 2;
- String result = getLongestRepeatedNonOverlappingSubstring(text, mid);
- if (result == null) {
- high = mid - 1;
- } else {
- best = result;
- low = mid + 1;
- }
- }
- return best;
- }
- private static String getLongestRepeatedNonOverlappingSubstring(String text, int length) {
- int n = text.length();
- Map<Long, Integer> hashToStartIndex = new HashMap<Long, Integer>();
- RollingHash rollingHash = new RollingHash(text.substring(0, length));
- hashToStartIndex.put(rollingHash.getHash(), 0);
- for (int start = 1, end = length; end < n; ++start, ++end) {
- rollingHash.remove(text.charAt(start - 1));
- rollingHash.add(text.charAt(end));
- long hash = rollingHash.getHash();
- if (hashToStartIndex.containsKey(hash)) {
- int prevStart = hashToStartIndex.get(hash);
- int substringLength = end - start + 1;
- int numCharsBetweenSubstrings = start - prevStart - substringLength;
- if (numCharsBetweenSubstrings >= 0) {
- return text.substring(start, end + 1);
- }
- } else {
- hashToStartIndex.put(hash, start);
- }
- }
- return null;
- }
- private static class RollingHash {
- private final int BASE = 256;
- private long BIG_PRIME;
- private long BIGGEST_BASE;
- private long hash = 0;
- public RollingHash(String initial) {
- int n = initial.length();
- this.BIG_PRIME = this.getLongRandomPrime();
- this.BIGGEST_BASE = 1;
- for (int i = 1; i < n; ++i) {
- this.BIGGEST_BASE = (this.BASE * this.BIGGEST_BASE) % this.BIG_PRIME;
- }
- for (int i = 0; i < n; ++i) {
- this.add(initial.charAt(i));
- }
- }
- public long getHash() {
- return this.hash;
- }
- public void add(char character) {
- this.hash = ((this.BASE * this.hash) + (int)character) % this.BIG_PRIME;
- }
- public void remove(char character) {
- this.hash = (this.hash + this.BIG_PRIME - ((int)character * this.BIGGEST_BASE) % this.BIG_PRIME) % this.BIG_PRIME;
- }
- private static long getLongRandomPrime() {
- BigInteger prime = new BigInteger(31, new Random());
- return prime.longValue();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement