求字符串中的最长重复子串

写在前面的话：前两天去面试Android，笔试的时候出现了这个问题。离开开发平台，拿笔手动写代码真心难受，再加上这样那样的原因，最终我思路很乱写的也不对，也不想再改了（在纸上改起来心好累），就递上去了。

回到家里，打开电脑，当我的手按在键盘上的时候，思路瞬间清晰了（这算是代码狗的被动Buff吗……）。

首先，我们来定义一个实体类，用于封装一个子串。

/**
 * 子串类
 * 
 * @author Li Hongtao
 *
 */
class SubStr {
private String str;// 子串
private int count;// 重复次数

public SubStr(String str, int count) {
this.str = str;
this.count = count;
}

//两个参数的set、get方法

……

}

然后是Main类：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Main {

private static String mString = "abcdefgaceaceacw";// 待检测字符串
private static Map<String, Integer> mMap = new HashMap<String, Integer>();// 所有子串集合<子串,重复次数>
private static List<SubStr> mList = new ArrayList<SubStr>();// 重复子串列表

public static void main(String[] args) {
for (int i = 0; i < mString.length(); i++) {// 遍历字符串的每个字符
for (int step = 1; step <= mString.length() - i; step++) {// 步长从1开始
String s = mString.substring(i, i + step);//取从第i个字符开始向后step个字符为子串
if (mMap.containsKey(s)) {// 如果该子串已存在于集合中
int count = mMap.get(s) + 1;// 取其保存于集合中的数量并+1
mMap.replace(s, count);// 更新结果集
} else {//如果集合中没有该子串，则存入
mMap.put(s, 1);
}
}
}//循环结束，我们遍历了字符串的所有子串，并利用HashMap键的唯一性保存了各子串重复出现的次数

//接下来遍历Map
for (Iterator<String> iterator = mMap.keySet().iterator(); iterator.hasNext();) {
String key = iterator.next();//键就是各个子串
int count = mMap.get(key);//获取该子串重复出现的次数
if (count == 1) {//如果只出现一次，就不是重复子串，pass掉
continue;
}
SubStr ss = new SubStr(key, count);//是重复子串，则生成实体对象
mList.add(ss);//保存到重复子串列表
}

mList.sort(new Comparator<SubStr>() {//使用自定义的Comparator来给列表排序


@Override
public int compare(SubStr o1, SubStr o2) {
return o2.getLength() - o1.getLength();//排序方式为子串的长度
}
});//这样我们就得到了按子串长度排序的重复子串列表

System.out.println("最长的重复字符串为: " + mList.get(0).getStr());
}

}

另外，如果是求重复出现次数最多的子串，只要把Comparator改写一下就行了：

mList.sort(new Comparator<SubStr>() {//使用自定义的Comparator来给列表排序

@Override
public int compare(SubStr o1, SubStr o2) {
return o2.getCount() - o1.getCount();//排序方式为子串重复出现的次数
}

});

好了，就这样了。

当然，这只是我个人的解法，不一定是最优的方案，仅供参考。