Android笔试题：求字符串中的最长重复子串

写在前面的话：前两天去面试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方法

……

/**获取子串长度*/

public int getlength() {

return str.length();

}

}

然后是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 mmap = new hashmap();// 所有子串集合<子串,重复次数>

private static list mlist = new arraylist();// 重复子串列表

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 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() {//使用自定义的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() {//使用自定义的comparator来给列表排序

@override

public int compare(substr o1, substr o2) {

return o2.getcount() - o1.getcount();//排序方式为子串重复出现的次数

}

});

好了，就这样了。

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