Created
April 15, 2017 15:53
-
-
Save hrishikesh-mishra/ffbf1a621c883e78ea65b476d1532e54 to your computer and use it in GitHub Desktop.
Longest Repeated Substring (using Suffix Array)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.hrishikesh.practices.string; | |
import java.util.Arrays; | |
/** | |
* Problem: | |
* Longest Repeated Substring (using Suffix Array) | |
* | |
* @author hrishikesh.mishra | |
*/ | |
public class LongestRepeatedSubstring { | |
public static String get(String s) { | |
int n = s.length(); | |
/** Creating suffix array **/ | |
String[] suffies = new String[n]; | |
for (int i = 0; i < n; i++) { | |
suffies[i] = s.substring(i); | |
} | |
/** Sorting suffix array **/ | |
Arrays.sort(suffies); | |
for (int i =0 ; i < suffies.length; i++){ | |
System.out.println(i + " :: " + suffies[i] ); | |
} | |
String result = ""; | |
/** Finding longest common prefix **/ | |
for (int i = 0; i < n - 1; i++) { | |
int len = getLongestCommonPrefix(suffies[i], suffies[i + 1]); | |
if (len > result.length()) { | |
result = suffies[i].substring(0, len); | |
} | |
} | |
return result; | |
} | |
private static int getLongestCommonPrefix(String s1, String s2) { | |
int len = 0; | |
for (int i = 0, j = 0; i < s1.length() && j < s2.length(); i++, j++) { | |
if (s1.charAt(i) != s2.charAt(j)){ | |
break; | |
} | |
len++; | |
} | |
return len; | |
} | |
} | |
class LongestRepeatedSubstringTest { | |
public static void main(String[] args) { | |
String s = "Such a funny, sporty, gamy, jesty, joky, hoky-poky lad, is the Ocean, oh!"; | |
String longestSuffix = LongestRepeatedSubstring.get(s); | |
System.out.println("String :" + s); | |
System.out.println("Longest Suffix String: " + longestSuffix); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment