文字列の最大長さを求めて、サブストリングを繰り返さないでください。
1888 ワード
一つの文字列の中の連続的なサブストリングを見つけました。このサブ串内にはどの文字も同じではなく、このサブストリングが一番長いです。例えば、abcdeabは、この文字列には重複しないサブストリングがたくさんあります。例えば、abcde、bcdea、cdeabは全部サブストリングを繰り返さないで、しかも一番長いです。試験例abceaefk abceaaaa
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class LongestsubString {
public static void main(String[] args) {
print(getLongestNoRepeatSubString("abceafb"));
}
private static void print(List list) {
for(Iterator it=list.iterator();it.hasNext();){
System.out.println(it.next());
}
}
public static List getLongestNoRepeatSubString(String src){
char[] arr=src.toCharArray();
int len=arr.length;//
List<String> subList=new ArrayList<String>();// ,
int max;//
int start;//
Map<Character,Integer> charMap=new HashMap();//
max=start=0;
int i;
for(i=0;i<len;i++){
if(!charMap.containsKey(arr[i])){// map
charMap.put(arr[i], i);
}else{// ,
int pre=charMap.get(arr[i]);
int tempLen=i-start;//
if(tempLen>=max){//
if(tempLen>max)subList.clear();//
max=tempLen;
subList.add(src.substring(start, i));//
charMap.put(arr[i], i);//
}else{
charMap.put(arr[i], i);//
}
start=pre+1;// , start
}
}
if(i-start>=max){// :abcd ~~
if(i-start>max)subList.clear();
subList.add(src.substring(start, i));
}
return subList;
}
}