# Longest repeating sub-sequence

Finding longest repeating sub-sequence or substring among a string is classic CS problem. Here is one simple solution where we use approach of finding all the substrings from beginning and sort the resulting array. In sorted array we will find longest common repeating sub-sequence.

Input: banana

Output: ana

//method to return longest subsequence
public static String findLongestSubsequence(String str)
{
String sub=””;

String arr[]=new String[str.length()];
//Firstly lets find all the substrings
for(int i=0;i<str.length();i++)
{
arr[i]=str.substring(i);
}

//as we have the list of all substrings, sort them
Arrays.sort(arr);

//compare strings with next string and find the maximum length common substring
for(int i=0;i<arr.length-1;i++)
{
//compare arr[i], arr[i+1]
int len=(arr[i].length()<arr[i+1].length())?arr[i].length():arr[i+1].length();
String temp=””;

for(int j=0;j<len;j++) { //compare two strings till a point where they are equal if(arr[i].charAt(j)==arr[i+1].charAt(j)) temp=arr[i].substring(0,j+1); else break; } sub=(temp.length()>sub.length())?temp:sub;
}

return sub;
}

There are other ways to find longest repeating sub-sequence. One  important way is to create a m*n matrix with a value showing length of subsequence till that point

b a n a n a
b   0 0 0 0 0 0
a   0 0 0 1 1 1
n   0 0 0 1 2 2
a   0 1 1 1 2 3
n   0 1 2 2 2 3
a   0 1 2 3 3 3

Another sophisticated way is to create a suffix tree. Read more here –http://en.wikipedia.org/wiki/Suffix_tree