java-两种方法求第一个最长的可重复子串

import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class MaxPrefix {

	
	public static void main(String[] args) {
		String str="abbdabcdabcx";
		//String str="ababa";
		MaxPrefix mp=new MaxPrefix();
		mp.findMaxPrefix2(str);
	}
	
	/*
	 * 1.find a[j]=a[i].(i<j)
	 * 2.k=i.(k++,j++)until a[k]!=a[j].count the length;if count>prefixLen,prefixLen=count. update the startIndex.
	 * 3.next i
	 */
	public void findMaxPrefix(String str){
		char[] chars=str.toCharArray();
		int len=str.length();
		int startIndex=0;
		int prefixLen=0;
		boolean found=false;
		for(int i=0;i<len;i++){
			int j=i+1;
			for(;j<len;j++){
				if(chars[j]==chars[i]){
					found=true;
					break;
				}
			}
			if(found){
				int count=0;
				int k=i;
				while(k<len&&j<len&&chars[k]==chars[j]){
					k++;
					j++;
					count++;
				}
				if(count>prefixLen){
					startIndex=k-count;
					prefixLen=count;
				}
			}
		}
		if(prefixLen!=0){
			System.out.println(prefixLen+",startIndex="+startIndex);
			for(int i=0;i<prefixLen;i++){
				System.out.print(chars[startIndex+i]);
			}
		}else{
			System.out.println("no duplicate char ");
		}
	}
	
	/*
	 * 使用后缀数组，具体思路参见http://blog.csdn.net/iamskying/article/details/4759485
	 * 不过
	 * 1.这个思路在生成后缀数组时，用“暴力”生成：先取最后1个元素，然后取最后2个元素、最后3个元素...
	 * 据说可以通过倍增算法和DC3算法，不过没研究过...
	 * 2.下面这个结论我不明白，后缀数组的原理还没研究过-->
	 * “将所有后缀数组按字典顺序排序后，两个相邻位置的后缀数组比较，取其最长公共前缀，即为所求字符串s的最长可重叠重复子串”
	 */
	public void findMaxPrefix2(String str){
		String[] suffixArray=generateSuffixArray(str);
		//string sort
		List<String> list = (List<String>) Arrays.asList(suffixArray);
		Collections.sort(list);
		
		//两个相邻位置的后缀数组比较，取其最长公共前缀
		//int startIndex=0;//只有第一个字符相同时，才有“公共前缀”
		int prefixLen=-1;
		int index=-1;
		for(int i=0,len=suffixArray.length;i<len-1;i++){
			char[] str1=suffixArray[i].toCharArray();
			char[] str2=suffixArray[i+1].toCharArray();
			int k1=0,k2=0;
			int len1=str1.length,len2=str2.length;
			int count=0;
			if(str1[0]==str2[0]){//只有第一个字符相同时，才有“公共前缀”
				while(k1<len1&&k2<len2&&str1[k1]==str2[k2]){
					k1++;
					k2++;
					count++;
				}
				if(count>prefixLen){
					prefixLen=count;
					index=i;
				}
			}
		}
		if(index!=-1){
			String str3=suffixArray[index];
			System.out.println("max SubString is "+str3.substring(0,prefixLen));
		}else{
			System.out.println("no duplicate char ");
		}
		
	}
	public String[] generateSuffixArray(String str){
		int len=str.length();
		String[] suffixArray=new String[len];
		for(int i=0;i<len;i++){
			int endIndex=len;
			int beginIndex=len-1-i;
			suffixArray[i]=str.substring(beginIndex, endIndex);
		}
		return suffixArray;
	}
}

评论

2 楼 无知的1234 2015-05-12  

第一个方法有错吧，如果在碰见一个字母相同后，后面相同的字母则不会再去比较了诶

1 楼 shenselongge 2014-04-03  

用abbdabcdabcxddddddeeeddd测试结果不正确