In this tutorial, you will learn how to write a java program to find the longest repeating sequence in a string. For example, if the given string is “abracadabra” then the longest repeating sequence in this string would be “abra”.
Highlighting longest re-occurring sequence in the string: abrakadabra.
Program to find the longest reoccurring sequence in a given String
In this program, we have a user defined method longestCP()
which determines which substring has the longest common prefix. In the main() method of the program, we are running a nested for loop and passing the substrings of the given string to the method we created, the method then returns the largest common prefix.
At the end of the loop, the largest common prefix is compared with the previously found largest repeating sequence and the largest between these two replaces the value of longestRS
.
public class JavaExample {
//This method returns the longest common prefix
//This will be called to determine which substring has
//the largest common prefix.
public static String longestCP(String s, String t){
int n = Math.min(s.length(),t.length());
for(int i = 0; i < n; i++){
if(s.charAt(i) != t.charAt(i)){
return s.substring(0,i);
}
}
return s.substring(0,n);
}
public static void main(String[] args) {
String str = "abracadabra";
String longestRS="";
int len = str.length();
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
String s =
longestCP(str.substring(i,len),str.substring(j,len));
if(s.length() > longestRS.length())
longestRS=s;
}
}
System.out.println("Longest repeating sequence" +
" in the given string is: "+longestRS);
}
}
Output:
Leave a Reply