这是一个与Nussinov算法类似的任务，实际上比它更简单，因为我们不允许在对齐中插入任何间隔、插入或不匹配。
对于长度为N的字符串A，定义一个F[-1 .. N, -1 .. N]表格，并使用以下规则填充：
for i = 0 to N
for j = 0 to N
if i != j
{
if A[i] == A[j]
F[i,j] = F [i-1,j-1] + 1;
else
F[i,j] = 0;
}
例如，对于B A O B A B：
此算法运行时间为O(n^2)。表中最大的值现在指向最长自我匹配子序列的终止位置（一个是i-一个出现的结尾，另一个是j-另一个出现的结尾）。开始时，数组被假定为零初始化。我已经添加了一个条件来排除对角线，因为那是最长但可能不是有趣的自匹配。
思考更多后，这个表在对角线上是对称的，因此只计算其中一半就足够了。另外，数组被零初始化，所以赋值为零是多余的。以上是原文。
for i = 0 to N
for j = i + 1 to N
if A[i] == A[j]
F[i,j] = F [i-1,j-1] + 1;
更短但可能更难理解。计算表包含所有匹配，短的和长的都有。您可以根据需要添加进一步筛选。
在下一步中，您需要从非零单元格沿对角线向上和向左恢复字符串。在此步骤中，使用一些哈希映射来计算相同字符串的自相似匹配数量也很简单。对于普通的字符串和普通的最小长度，只有少量的表格单元格会通过该映射进行处理。
我认为直接使用哈希映射实际上需要O(n^3)，因为在访问结束时必须以某种方式比较关键字字符串是否相等。这种比较可能是O(n)。
Python. 这有点粗糙，数据结构起到了大部分的作用。
from collections import Counter
accumulator = Counter()
text = 'hello world this is hello world.'
for length in range(1,len(text)+1):
for start in range(len(text) - length):
accumulator[text[start:start+length]] += 1
for start in range(len(text) - length) 并删除 if。 - Jon Purdyaccumulator.most_common()。 - jfs由于对于长度大于等于2的字符串的每个子串，文本中至少包含一个长度为2的子串至少同样多次，因此我们只需要研究长度为2的子串。
val s = "hello world this is hello world. hello world repeats three times in this string!"
val li = s.sliding (2, 1).toList
// li: List[String] = List(he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " t", th, hi, is, "s ", " i", is, "s ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, d., ". ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " r", re, ep, pe, ea, at, ts, "s ", " t", th, hr, re, ee, "e ", " t", ti, im, me, es, "s ", " i", in, "n ", " t", th, hi, is, "s ", " s", st, tr, ri, in, ng, g!)
val uniques = li.toSet
uniques.toList.map (u => li.count (_ == u))
// res18: List[Int] = List(1, 2, 1, 1, 3, 1, 5, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 1, 3, 3, 2, 4, 1, 2, 2, 1)
uniques.toList(6)
res19: String = "s "
这只是伪代码，也许这不是最优美的解决方案，但我会像这样解决：
function separateWords(String incomingString) returns StringArray{
//Code
}
function findMax(Map map) returns String{
//Code
}
function mainAlgorithm(String incomingString) returns String{
StringArray sArr = separateWords(incomingString);
Map<String, Integer> map; //init with no content
for(word: sArr){
Integer count = map.get(word);
if(count == null){
map.put(word,1);
} else {
//remove if neccessary
map.put(word,count++);
}
}
return findMax(map);
}
在 Java HashMap 中，map 可以包含键值对。
Perl，O(n²)解决方案
my $str = "hello world this is hello world. hello world repeats three times in this string!";
my @words = split(/[^a-z]+/i, $str);
my ($display,$ix,$i,%ocur) = 10;
# calculate
for ($ix=0 ; $ix<=$#words ; $ix++) {
for ($i=$ix ; $i<=$#words ; $i++) {
$ocur{ join(':', @words[$ix .. $i]) }++;
}
}
# display
foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) {
print "$_: $ocur{$_}\n";
last if !--$display;
}
显示最常见子字符串的前10个最佳分数（如果存在平局，则先显示最长的单词链）。将$display更改为1以仅获取结果。
共有n（n + 1）/ 2次迭代。
O(n)中的直方图可以轻松找到它。 - amithello world”；但子字符串hello world仅出现三次，而子字符串l出现了九次。（而is出现了四次。而“ ”出现了十五次。） - ruakh