一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc

Question

一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。求解答

Answer 1

abczzacbca,为什么zz不算啊？zz也是长2啊应该是重复最多的吧。。

Answer 2

貌似是面试题。。考hashmap的。。

Answer 3

最长的当然是bc了，hashmap已经忘得差不多了，观望

Answer 4

找出最长的重复子串 zz 只出现过一次 而bc出现过两次

Answer 5

public static void main(String[] args) {
String s = "abczzacbca";
String temp = null;
int tempLen = 0;
char[] c = s.toCharArray();
Map<String, Integer> m = new HashMap<String, Integer>();
for (int i = 0; i < c.length - 1; i++) {
temp = c[i] + "" + c[i + 1];
tempLen = i + 1;
while (s.indexOf(temp.toString()) != tempLen) {
if (m.containsKey(temp.toString())) {
m.put(temp, m.get(temp) + 1);
} else {
m.put(temp, 1);
}
tempLen++;
if (tempLen >= c.length) {
break;
} else {
temp += c[tempLen];
}
}
}
Map<String, Integer> m1 = new HashMap<String, Integer>();
// 去掉值为1的子串
for (Entry<String, Integer> e : m.entrySet()) {
if (e.getValue() != 1) {
m1.put(e.getKey(), e.getValue());
}
}
if(m1.size()==0){
System.out.println("没有最长子串！");
}else{
// 取出最大的子串
int max = 0;
for (Entry<String, Integer> e : m1.entrySet()) {
if(e.getValue()>max){
max = e.getValue();
}
}
StringBuffer sb = new StringBuffer();
for (Entry<String, Integer> e : m1.entrySet()) {
if(e.getValue()==max){
sb.append(e.getKey());
sb.append(",");
}
}
System.out.println("最长子串为："+sb.substring(0, sb.length()-1)+"  长度为："+max);
}

}没优化的 
不知道对10000的字符串有没有效果 
1000一下的应该是没问题的

Answer 6

public void test3(){
String str = "abczzacbca";
int strlen = str.length();
int findlen = 2;
int pointer = 0;
for(int i = 0; i < strlen - 2; i++){
String toFind = str.substring(pointer, pointer+findlen);
for(int j = pointer+2; j < strlen-2;j++){
String comp = str.substring(j,j+findlen);
System.out.println(find(str, toFind, comp, pointer, j,findlen));
}
pointer++;
}
}

public String find(String str, String toFind, String comp, int pointer, int compPointer, int findlen){
String found = "";
String lastFound = toFind;
if(toFind.equals(comp)){
findlen++;
toFind = str.substring(pointer,pointer+findlen);
comp = str.substring(compPointer+findlen);
if(pointer < compPointer){
found = find(str, toFind, comp, pointer, compPointer,findlen);
if(found == ""){
found = lastFound;
}
}
}
return found;
}

Answer 7

稍微优化了下:
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
String s = "abczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbca"
  +"abczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbcaabczzacbca"
  +"";
test1(s);
long endTime = System.currentTimeMillis();
System.out.println("花费时间为："+((double)(endTime-startTime))/1000+"秒");
}

public static void test1(String s){
String temp = null;
int tempLen = 0;
char[] c = s.toCharArray();
Map<String, Integer> m = new HashMap<String, Integer>();
for (int i = 0; i < c.length - 1; i++) {
temp = c[i] + "" + c[i + 1];
tempLen = i + 1;
while (s.indexOf(temp)!=s.lastIndexOf(temp)) {
if (m.containsKey(temp.toString())) {
m.put(temp, m.get(temp) + 1);
} else {
m.put(temp, 1);
}
tempLen++;
if (tempLen >= c.length) {
break;
} else {
temp += c[tempLen];
}
}
}
System.out.println("s的长度为："+s.length());
Map<String, Integer> m1 = new HashMap<String, Integer>();
// 去掉值为1的子串
for (Entry<String, Integer> e : m.entrySet()) {
if (e.getValue() != 1) {
m1.put(e.getKey(), e.getValue());
}
}
if(m1.size()==0){
System.out.println("没有最长子串！");
}else{
// 取出最大的子串
int max = 0;
for (Entry<String, Integer> e : m1.entrySet()) {
if(e.getValue()>max){
max = e.getValue();
}
}
StringBuffer sb = new StringBuffer();
for (Entry<String, Integer> e : m1.entrySet()) {
if(e.getValue()==max){
sb.append(e.getKey());
sb.append(",");
}
}
System.out.println("最长子串为："+sb.substring(0, sb.length()-1)+"  长度为："+max);
}
}
s的长度为：2000
最长子串为：bc  长度为：400
花费时间为：19.766秒s的字符串为2000需要20秒 3000就会内存溢出 需要加大JVM内存