算法实践--设想与实现的差距
一个面试题目，从任意的字符串中找到最长的重复的子字符串，例如：abdcefgbdfcef中最长的重复子串是cef。
刚看到这个题目的时候，我想到了穷举法，不再赘述；只是穷举的方式可以选择子串长度从n/2到2，或者从2到n/2。
第二个方案想到了使用树记录重复的子串，长度最大的重复的枝杈即是解。在思考细节时发现不好处理同字母重复问题，例如：aabaaaabaa。
第三个方案想到使用动态规划的方法，以aabaaaabaa为例，过程可以描述为a,a->a,a,b->a,a,b,a->aa,b,aa->aa,b,aa,a->aa,b,aa,aa->aab,aa,aab->aaba,a,aaba->aabaa,aabaa，考虑到这个算法的效率优于穷举法，所以从设想开始着手实现。
在编写代码的过程中，发现可以利用倒排表，先记录某个字符出现的位置，然后来减少查找的比较的次数。这个设想直接改变了对于算法的设计。最后是我的算法实现。
所以，把设想真正实现，是表达设想的最有效的途径，同时也可以重新审视自己的设想。
最后实现：
private static void search(final StringBuilder buff) {
final List<String> indexes = new LinkedList<>();
final Map<Character, List<Integer>> charStartMap = new HashMap<Character, List<Integer>>();
for (int n = 0, len = buff.length(); n < len; n++) {
final char c = buff.charAt(n);
List<Integer> offsetList = charStartMap.get(c);
if (offsetList == null) {
offsetList = new ArrayList<>();
offsetList.add(n);
charStartMap.put(c, offsetList);
} else {
offsetList.add(n);
for (final int offset : offsetList) {
final StringBuilder tempBuff = new StringBuilder();
tempBuff.append(c);
for (int m = (offset + 1); m < n; m++) {
if (n + m - offset >= len) {
break;
}
if (buff.charAt(m) == buff.charAt(n + (m - offset))) {
tempBuff.append(buff.charAt(m));
} else {
break;
}
}
if (indexes.size() > 0
&& indexes.get(0).length() < tempBuff.length()) {
indexes.clear();
}
if (indexes.size() == 0
|| indexes.get(0).length() == tempBuff.length()) {
indexes.add(tempBuff.toString());
}
}
}
}
for (final String s : indexes) {
System.out.println(s);
}
}
备注：该算法在处理同一个字符的重复字串时，性能不如穷举法，解决方法是编写预处理程序，对付特例。