在我看来，无论你选择哪种方法来实现它，通常都会有自己的最坏情况。
不同之处在于其最坏情况的性能。
例如，我已经在我的电脑上测试了isnot2bad的方法、我的第一次实现（oneTry）和我的第二次实现（secondTry）。
最坏情况的测试结果如下：
isnot2bad的方法：~330秒（2*10^5），~74秒（10^5），~0.8秒（10^4），~0.01秒（10^3）
我的第一次实现（oneTry）：~200秒（2*10^5），~45秒（10^5），~0.5秒（10^4），~0.01秒（10^3）
我的第二次实现（secondTry）：~4秒（10^6），~0.4秒（10^5），~0.05秒（10^4），~0.007秒（10^3）
从测试结果可以看出，“secondTry”的最坏性能时间几乎是线性的，而其他方法则几乎是平方的。
secondTry 实现的想法如下：
对于任何字符串输入
T(T0...Tn-1, len=n),，总字符串的相似度值(
St)是字符串 S 中每个单独字符的相似度值(
Si)的总和。
例如：St = S0 + ...+Si+...+Sn-1
显然，子串[T0...Ti]中 T0 的总数大于等于 Si 大于等于 1。
Si 的确切值等于子串 [T0...Ti] 中 T0 的总数，这些 T0 连续匹配到 Ti。
例如：T="aabaab"，则 T2='b'，只有 T0('a') 可以继续到 T2，而 T1('a') 无法继续到 T2。因此，S2=1。
因此，我们需要跟踪哪些 T0 被继续使用了（如果是，将其保留在数组中；否则，从数组中删除它）。然后，就可以轻松计算每个 Ti 的相似度。
同时，为了提高性能，我们不需要检查每个连续的 T0。实际上，对于一些 T0，它们可以合并在一起。因为它们属于重复模式。（可能是长模式或短模式）。
例如：
ababababab... ：T0、T2、T4、T6... 可以合并为一个整体。
aaaaaaaaaa... ：T0、T1、T2、T3... 可以合并为一个整体。
aaaabaaaabaaaab...：
T0、T5、T10、T15... 可以合并成一个整体。
T1、T2、T3 可以合并成一个整体。
T6、T7、T8 可以合并成一个整体。
...
详细的实现代码如下所示。
希望有人能够发布他们在这个主题上的最佳实现和测试结果。
谢谢。
public static List<ANode> anodes = null;
public static List<ANode> tnodes = null;
public static void checkANodes(CharSequence input, int num) {
tnodes = new Vector<ANode>();
for(int i=anodes.size()-1; i>=0; i--) {
ANode anode = anodes.get(i);
if(input.charAt(num) == input.charAt(num-anode.pos)) {
tnodes.add(anode);
}else {
if(tnodes.size() > 0) {
ANode after = tnodes.get(tnodes.size()-1);
tnodes.remove(after);
if(after.c > 1) {
tnodes.add(new ANode(after.pos + after.shift, after.shift ,after.c-1));
tnodes.add(new ANode(after.pos, after.pos-anode.pos + anode.shift,1));
}else {
tnodes.add(new ANode(after.pos, after.pos-anode.pos + anode.shift,1));
}
}
}
}
anodes.clear();
for(int i=tnodes.size() - 1; i >= 0; i--) {
anodes.add(tnodes.get(i));
}
}
public static int secondTry(CharSequence input) {
anodes = new Vector<ANode>();
int start = 0;
for (int i = 1; i < input.length(); i++) {
if (input.charAt(i) == input.charAt(0)) {
start = i;
break;
}
}
int count = 0;
int base = 0;
for (int i = start; i < input.length(); i++) {
checkANodes(input, i);
if(input.charAt(0) == input.charAt(i)) {
if(anodes.size() == 0) {
anodes.add(new ANode(i, i, 1));
}else {
ANode last = anodes.get(anodes.size()-1);
int shift = i - last.pos;
int mod = shift % last.shift;
if(mod == 0) {
last.c++;
}else {
anodes.add(new ANode(i, mod, 1));
}
}
}
base = 0;
for(ANode anode : anodes) {
base = base + anode.c;
}
count = count + base;
}
count = count + input.length();
return count;
}
public class ANode {
public int pos = 0;
public int c = 1;
public int shift = 0;
public ANode(int pos, int shift, int c) {
this.pos = pos;
this.shift = shift;
this.c = c;
}
}
