similar_text是如何工作的？

这实际上是一个非常有趣的问题，谢谢你给我一个谜题，结果非常有益。

让我首先解释一下similar_text是如何工作的。

类似文本：算法

这是一种基于递归的分而治之算法。它的工作原理是首先找到两个输入之间最长的公共字符串，然后将问题分解为围绕该字符串的子集。

您在问题中使用的示例实际上都只执行算法的一次迭代。唯一不使用一次迭代和给出不同结果的那些来自 php.net 注释。

这里有一个简单的例子，可以理解simple_text背后的主要问题，并希望能对它的工作原理有一些了解。

类似文字：缺陷

eeeefaaaaafddddd
ddddgaaaaagbeeee

Iteration 1:
Max    = 5
String = aaaaa
Left : eeeef and ddddg
Right: fddddd and geeeee

我希望这个缺陷已经很明显了。它只会直接检查两个输入字符串中最长匹配字符串的左侧和右侧。此示例

$s1='eeeefaaaaafddddd';
$s2='ddddgaaaaagbeeee';

echo similar_text($s1, $s2).'|'.similar_text($s2, $s1);
// outputs 5|5, this is due to Iteration 2 of the algorithm
// it will fail to find a matching string in both left and right subsets

说实话，我不确定应该如何对待这个案子。可以看出，字符串中只有2个字符不同。但是eeee和dddd都处于两个字符串的两端，不确定NLP爱好者或其他文学专家对这种特定情况的看法。

类似文本：参数交换时的结果不一致

您根据输入顺序遇到的不同结果是由于alogirthm的实际行为方式（如上所述）。我将对正在发生的事情进行最后的阐述。

echo similar_text('test','wert'); // 1
echo similar_text('wert','test'); // 2

在第一种情况下，只有一个迭代：

test
wert

Iteration 1:
Max    = 1
String = t
Left :  and wer
Right: est and 

我们只有一次迭代，因为空/空字符串在递归时返回 0。所以这结束了算法，我们得到了我们的结果：1

然而，在第二种情况下，我们面临着多次迭代：

wert
test

Iteration 1:
Max    = 1
String = e
Left : w and t
Right: rt and st

我们已经有一个长度为 1 的通用字符串。左侧子集上的算法将以 0 个匹配项结束，但在右侧：

rt
st

Iteration 1:
Max    = 1
String = t
Left : r and s
Right:  and 

这将导致我们的新的和最终的结果：2

我感谢你提出这个内容非常丰富的问题，并有机会再次涉足C++。

类似文本： JavaScript Edition

简短的回答是：javascript代码没有实现正确的算法

sum += this.similar_text(first.substr(0, pos2), second.substr(0, pos2));

显然应该是first.substr(0,pos1)

注意：JavaScript 代码已由 eis 在之前的提交中修复。谢谢@eis

揭开神秘面纱！

看起来该函数确实根据参数顺序使用不同的逻辑。我认为有两件事在起作用。

首先，请参阅此示例：

echo similar_text('test','wert'); // 1
echo similar_text('wert','test'); // 2

它似乎正在测试“在param2中找到param1上任何不同字符的次数”，因此，如果您交换参数，结果会有所不同。它已被报告为一个错误，该错误已被关闭为“按预期工作”。

现在，对于PHP和javascript实现来说，上述内容是相同的 - paremeter顺序有影响，所以说JS代码不会这样做是错误的。这在 bug 条目中被认为是预期的行为。

其次 - 似乎不正确的是MYSQL / PHP单词示例。有了这个，javascript版本给出了3个与参数顺序无关的参数，而PHP给出了2和3（因此，百分比同样不同）。现在，短语“PHP IS GREAT”和“WITH MYSQL”应该有5个共同的字符，与你比较的方式无关：H，I，S和T，各一个，加上一个空白空间。为了让它们有3个字符，'H'，''和'S'，所以如果你看一下顺序，正确答案应该是3个双向。我将C代码修改为可运行版本，并添加了一些输出，因此可以看到那里发生了什么（codepad链接）：

#include<stdio.h>

/* {{{ php_similar_str
 */
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  int l;

  *max = 0;
  for (p = (char *) txt1; p < end1; p++) {
    for (q = (char *) txt2; q < end2; q++) {
      for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
      if (l > *max) {
        *max = l;
        *pos1 = p - txt1;
        *pos2 = q - txt2;
      }
    }
  }
}
/* }}} */


/* {{{ php_similar_char
 */
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
  int sum;
  int pos1, pos2, max;

  php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);

  if ((sum = max)) {
    if (pos1 && pos2) {
      printf("txt here %s,%s\n", txt1, txt2);
      sum += php_similar_char(txt1, pos1,
                  txt2, pos2);
    }
    if ((pos1 + max < len1) && (pos2 + max < len2)) {
      printf("txt here %s,%s\n", txt1+ pos1 + max, txt2+ pos2 + max);
      sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
                  txt2 + pos2 + max, len2 - pos2 - max);
    }
  }

  return sum;
}
/* }}} */
int main(void)
{
    printf("Found %d similar chars\n",
        php_similar_char("PHP IS GREAT", 12, "WITH MYSQL", 10));
    printf("Found %d similar chars\n",
        php_similar_char("WITH MYSQL", 10,"PHP IS GREAT", 12));
    return 0;
}

结果是输出：

txt here PHP IS GREAT,WITH MYSQL
txt here P IS GREAT, MYSQL
txt here IS GREAT,MYSQL
txt here IS GREAT,MYSQL
txt here  GREAT,QL
Found 3 similar chars
txt here WITH MYSQL,PHP IS GREAT
txt here TH MYSQL,S GREAT
Found 2 similar chars

因此，可以看到，在第一次比较时，函数找到了“H”，“”和“S”，但没有找到“T”，并得到3的结果。第二个比较发现“I”和“T”，但没有找到“H”，“”或“S”，因此得到的结果为2。

从输出中可以看出这些结果的原因：算法获取第二个字符串包含的第一个字符串中的第一个字母，对其进行计数，并从第二个字符串中丢弃在此之前的字符。这就是为什么它错过了介于两者之间的字符，这就是当你改变字符顺序时导致差异的原因。

那里发生的事情可能是故意的，也可能不是。但是，这不是javascript版本的工作方式。如果你在javascript版本中打印出同样的东西，你会得到这个：

txt here: PHP, WIT
txt here: P IS GREAT,  MYSQL
txt here: IS GREAT, MYSQL
txt here: IS, MY
txt here:  GREAT, QL
Found 3 similar chars
txt here: WITH, PHP 
txt here: W, P
txt here: TH MYSQL, S GREAT
Found 3 similar chars

显示javascript版本以不同的方式做到这一点。javascript版本所做的是，它发现“H”，“”和“S”在第一次比较中的顺序相同，在第二次比较中也具有相同的“H”，“”和“S” - 所以在这种情况下，参数的顺序无关紧要。

由于javascript旨在复制PHP函数的代码，因此它需要具有相同的行为，因此我根据对@Khez和修复的分析提交了错误报告，该修复程序现已合并。