当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-01-07   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Collections; import java.util.List; public class MaxPrefix { public static void main(String[] args) { String str="abbdabcdabcx";
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;
	}
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
  题意:求一个字符串里两个不重叠的最长重复子串 代码如下: 1 #include<cstdio> 2 #inclu
求最长回文串,如果是暴力的方法的话,会枚举每个字符为中心,然后向两边检测求出最长的回文串,时
题意:给一字符串,求一个子串的长度,该子串满足所有字符都不重复。字符可能包含标点之类的,不仅
首先:大家都知道什么叫回文串吧,这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算
题目:求解两个字符串的最长公共子串长度 有两个字符串S1和S2,求一个最长公共子串,即求字符串S3,
时间复杂度O(n) 算法的主要思想是从左到右处理字符串,求每个位置为中心的两端对称的最大半径。 v
Manacher算法是用来求解一个给定字符串的最长回文子串,回文就是将字符串翻转后,与原来一样。这个
From: http://bbs.dlut.edu.cn/bbstcon.php?board=Competition&gid=23474 From: http://www.felix02
作者:寒小阳 时间:2013年9月。 出处:http://blog.csdn.net/han_xiaoyang/article/details/119694
烟台大学计算机学院学生 *All rights reserved. *文件名称:求最小公倍数的两种方法!!! *作者:杨
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号