求一个串中出现的的第一个最长重复子串

Question

求一个串中出现的的第一个最长重复子串
public class J{
public static void main(String[] args) {
  String str="abbdabcdabcxkkkkkk";   
  J j=new J();
  j.find(str);
}
public void find(String s){
char arry[]=s.toCharArray();
int index=0,length=0,length1,i=0,k,j;
while(i<arry.length){
j=i+1;
while(j<arry.length){
if(arry[i]==arry[j]){
length1=1;
for(k=1;arry[i+k]==arry[j+k];k++)//查找有多少个相同的
length1++;
if(length1>length){//确定是最长子串
index=i;
length=length1;
}
j+=length1;
}
else
j++;
}
i++;
}
for(int m=0;m<length;m++){
System.out.print(""+arry[index+m]);
}
}
}
运行时报错
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 18
at J.find(J.java:15)
at J.main(J.java:5)

Answer 1

lz 参考这里 大牛们给出了简洁高效的算法。。http://topic.csdn.net/u/20120423/11/dbd47ed4-f59f-469a-8ffc-1126cc02fa4d.html

Answer 2

at J.find(J.java:15)
报越界了 ，单步调试一下

Answer 3

程序报Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 18
是因为数组下标溢出而报的错，在程序第15行for(k=1;arry[i+k]==arry[j+k];k++)语句中当j+k>=arry.length时arry数组下标越界而报错。arry数组的下标只能小于arry.length。修改后程序为：public class J {
public static void main(String[] args) {
String str = "abbdabcdabcxkkkkkk";
J j = new J();
j.find(str);
} public void find(String s) {
char arry[] = s.toCharArray();
int index = 0, length = 0, length1, i = 0, k, j;
while (i < arry.length) {
j = i + 1;
while (j < arry.length) {
if (arry[i] == arry[j]) {
length1 = 1;
for (k = 1; j+k<arry.length; k++)
if(arry[i + k] == arry[j + k]){
length1++;
}
// 查找有多少个相同的
if (length1 > length) {// 确定是最长子串
index = i;
length = length1;
}
j += length1;
} else
j++;
}
i++;
}
for (int m = 0; m < length; m++) {
System.out.print("" + arry[index + m]);
}
}
}

Answer 4

可以改成：for (k = 1;j + k<arry.length && arry[i + k] == arry[j + k]; k++)length1++;

Answer 5

就是求解一个字符串中的最大子串，例如abcdrtfabcd则输出abcd因为abcd是该串中最大的重复子串

Answer 6

public class J {
public static void main(String[] args) {
String str = "abbdabcdabcxkkkkkk";
J j = new J();
j.find(str);
} public void find(String s) {
char arry[] = s.toCharArray();
int index = 0, length = 0, length1, i = 0, k, j;
while (i < arry.length) {
j = i + 1;
while (j < arry.length) {
if (arry[i] == arry[j]) {
length1 = 1;
for (k = 1; j + k < arry.length; k++){
if (arry[i + k] == arry[j + k]) { 
length1++;
}
else      //   如果比较过程中，第一次出现不相等的就结束整个循环  否则就会一直往后比较了
break;
}
// 查找有多少个相同的

if (length1 > length) {// 确定是最长子串
index = i;
length = length1;
}
j += length1;
} else
j++;
}
i++;
}
for (int m = 0; m < length; m++) {
System.out.print("" + arry[index + m]);
}
}
}
如果出现连续的就不行了,上面限制不了这个条件，你想想看有没有什么办法  比如kkkkkk  

Answer 7

package regex;public class zccfzcinsamestr { /**
 * @param args
 */
public static void main(String[] args) {
String str = "asdaasdasdddd";
String maxStr = "";
for (int i = 0; i <= str.length() - 1; i++) {
for (int j = i + 2; j <= str.length(); j++) {
String cur = isRepeated(str, i, j); // System.out.println(str.substring(i, j) + " " + i + " " + j);
if (cur.length() > maxStr.length()) {
maxStr = cur;
}
}
} System.out.println(maxStr);
} static String isRepeated(String str, int start, int end) {
String cur = str.substring(start, end);
String before, after;
before = str.substring(0, start);
after = str.substring(end);
if (before.contains(cur) || after.contains(cur)) {
return cur;
}
return "";
}
}