文字列の最大長さを求めて、サブストリングを繰り返さないでください。

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;
	}
}