Advertisement
Guest User

Longest Repeated Non-overlapping Substring

a guest
Jun 28th, 2015
667
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.29 KB | None | 0 0
  1. import java.math.BigInteger;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.Random;
  5.  
  6. public class LongestRepeatedNonOverlappingSubstring {
  7.     public static void main(String[] args) {
  8.         String text = "abcabca";
  9.         String repeated = getLongestRepeatedNonOverlappingSubstring(text);
  10.  
  11.         System.out.println(repeated);
  12.     }
  13.  
  14.     public static String getLongestRepeatedNonOverlappingSubstring(String text) {
  15.         if (text == null) {
  16.             throw new IllegalArgumentException("Must pass in a non-null string!");
  17.         }
  18.  
  19.         int n = text.length();
  20.         int low = 1;
  21.         int high = n;
  22.         String best = "";
  23.  
  24.         while (low <= high) {
  25.             int mid = low + (high - low) / 2;
  26.             String result = getLongestRepeatedNonOverlappingSubstring(text, mid);
  27.  
  28.             if (result == null) {
  29.                 high = mid - 1;
  30.             } else {
  31.                 best = result;
  32.                 low = mid + 1;
  33.             }
  34.         }
  35.  
  36.         return best;
  37.     }
  38.  
  39.     private static String getLongestRepeatedNonOverlappingSubstring(String text, int length) {
  40.         int n = text.length();
  41.         Map<Long, Integer> hashToStartIndex = new HashMap<Long, Integer>();
  42.         RollingHash rollingHash = new RollingHash(text.substring(0, length));
  43.  
  44.         hashToStartIndex.put(rollingHash.getHash(), 0);
  45.  
  46.         for (int start = 1, end = length; end < n; ++start, ++end) {
  47.             rollingHash.remove(text.charAt(start - 1));
  48.             rollingHash.add(text.charAt(end));
  49.  
  50.             long hash = rollingHash.getHash();
  51.  
  52.             if (hashToStartIndex.containsKey(hash)) {
  53.                 int prevStart = hashToStartIndex.get(hash);
  54.                 int substringLength = end - start + 1;
  55.                 int numCharsBetweenSubstrings = start - prevStart - substringLength;
  56.  
  57.                 if (numCharsBetweenSubstrings >= 0) {
  58.                     return text.substring(start, end + 1);
  59.                 }
  60.             } else {
  61.                 hashToStartIndex.put(hash, start);
  62.             }
  63.         }
  64.  
  65.         return null;
  66.     }
  67.  
  68.     private static class RollingHash {
  69.         private final int BASE = 256;
  70.         private long BIG_PRIME;
  71.         private long BIGGEST_BASE;
  72.         private long hash = 0;
  73.  
  74.         public RollingHash(String initial) {
  75.             int n = initial.length();
  76.  
  77.             this.BIG_PRIME = this.getLongRandomPrime();
  78.             this.BIGGEST_BASE = 1;
  79.  
  80.             for (int i = 1; i < n; ++i) {
  81.                 this.BIGGEST_BASE = (this.BASE * this.BIGGEST_BASE) % this.BIG_PRIME;
  82.             }
  83.  
  84.             for (int i = 0; i < n; ++i) {
  85.                 this.add(initial.charAt(i));
  86.             }
  87.         }
  88.  
  89.         public long getHash() {
  90.             return this.hash;
  91.         }
  92.  
  93.         public void add(char character) {
  94.             this.hash = ((this.BASE * this.hash) + (int)character) % this.BIG_PRIME;
  95.         }
  96.  
  97.         public void remove(char character) {
  98.             this.hash = (this.hash + this.BIG_PRIME - ((int)character * this.BIGGEST_BASE) % this.BIG_PRIME) % this.BIG_PRIME;
  99.         }
  100.  
  101.         private static long getLongRandomPrime() {
  102.             BigInteger prime = new BigInteger(31, new Random());
  103.  
  104.             return prime.longValue();
  105.         }
  106.     }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement