学步园

I wrote the a program to get the Longest Repeated Substring of a string. I think the way I used should be Dynamic Programming. The basic steps are:
1) First find all Repeated Substrings with only one character
2) Find Repeated Substrings with the number of characters one character more than previous one and grow from previous one.
3) Repeat step 2 untill they stop growing.

In my way, the program's time complexity is O(n^2).  After searching the internet, I found there are other quicker way to achieve this. That is through Suffix Tree. Many string related algorithms are based on it. There's O(n) algorithm to build a Suffix Tree.

Several data structures is relevant to Suffix Tree, e.g. Suffix Array, Trie, etc.

Followed the program written in my own way. In some other time I'll try to learn Suffix Tree and Trie and Suffix Array.

Based on my understanding, Dynamic Programing has characters followed:
1)Problem solving is divided to steps.
2)Latter steps make use of former steps, and not recalculate from the beginning.
3)Getting rid of some former steps' results if they are found unapplicable to the problem in latter steps.

/*<br /> *.java<br /> suffix tree<br /> suffix array<br /> trie<br /> dynamic programming<br /> longest repeated substring problem<br /> */</p> <p>import java.io.IOException;<br /> import java.io.Reader;<br /> import java.io.BufferedReader;<br /> import java.io.InputStreamReader;<br /> import java.util.ArrayList;</p> <p>class SubSeqRepr{<br /> int orig;<br /> int start;<br /> int len;<br /> }<br /> public class SubSeq {<br /> public static void main(String[] args) {<br /> while(true) {<br /> System.out.println("Input a string, enter exit to terminate:");<br /> BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));<br /> String line=null;<br /> try{<br /> line=reader.readLine();<br /> }<br /> catch (IOException e){<br /> System.out.println("exception happened.");<br /> break;<br /> }<br /> if(line.equals("exit")) break;<br /> SubSeqRepr repr=maxRepSubSeq(line);<br /> if(repr==null){<br /> System.out.println("No repeated sub sequence.");<br /> }else {</p> <p> System.out.println("First repeated sub sequence with max len is at index "<br /> + repr.orig<br /> + " and "<br /> + repr.start<br /> + ". It is "<br /> + line.substring(repr.start,repr.start+repr.len)<br /> +"."<br /> );<br /> }<br /> }<br /> }</p> <p> static ArrayList<SubSeqRepr> getSubSeqReprOfLen1(String str){<br /> int i=0, outer=0;<br /> ArrayList<SubSeqRepr> list=new ArrayList<SubSeqRepr>();<br /> for(outer=0;outer<str.length();++outer) {<br /> for(i = outer+1;i<str.length();++i){<br /> if(str.substring(i,i+1).equals(str.substring(outer,outer+1))){<br /> SubSeqRepr repr=new SubSeqRepr();<br /> repr.orig=outer;<br /> repr.start=i;<br /> repr.len=1;<br /> list.add(repr);<br /> }<br /> }<br /> }<br /> return list;<br /> }</p> <p> static boolean getSubSeqReprOfLen(String str,ArrayList<SubSeqRepr> list,int len){<br /> SubSeqRepr repr=null;<br /> int i=0;<br /> boolean result=false;<br /> for(i = 0;i<list.size();++i){<br /> repr=list.get(i);<br /> if(repr.orig+len>str.length()) continue;<br /> if(repr.start+len>str.length()) continue;<br /> if(str.substring(repr.orig,repr.orig+len).equals(str.substring(repr.start,repr.start+len))){<br /> repr.len=len;<br /> result=true;<br /> }<br /> }<br /> for(i = list.size()-1;result && i>=0;i--){<br /> repr=list.get(i);<br /> if(repr.len<len){<br /> list.remove(i);<br /> }<br /> }<br /> return result;<br /> }</p> <p> static SubSeqRepr maxRepSubSeq(String str){<br /> int i=0;<br /> ArrayList<SubSeqRepr> list=null;<br /> for(i = 0;i<str.length()-1 ;++i){<br /> if(i==0){<br /> list=getSubSeqReprOfLen1(str);<br /> }else {<br /> if(!getSubSeqReprOfLen(str,list,i+1)) break;<br /> }<br /> }<br /> if(list.size()==0) return null;<br /> return list.get(0);<br /> }</p> <p>}<br />

Outputs of program:

Input a string, enter exit to terminate:<br /> 12341234<br /> First repeated sub sequence with max len is at index 0 and 4. It is 1234.<br /> Input a string, enter exit to terminate:<br /> mississippi<br /> First repeated sub sequence with max len is at index 1 and 4. It is issi.<br /> Input a string, enter exit to terminate:<br /> exit</p> <p>Process finished with exit code 0