-1

我想在 C++ 中创建一个字符串比较脚本。
Total Commander 文件比较功能相当不错：

总指挥官样本


这个算法是如何工作的？
有人可以分享这个功能的片段吗？

4

3 回答 3

2

我不能告诉你，总司令是做什么的。也许有人可以拆开它并尝试追踪技术。

但是一个常见的算法是这个：

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

一种字符串搜索算法。它肯定也有助于比较。

另请参阅这篇文章： c++ 字符串比较算法

此致

于 2013-04-16T09:30:55.583 回答
1

您可以使用 diff 或 LCS 算法进行这种比较。

下面是它的一个简单的 C 实现：

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int lcs(const char* s1, const char* s2)
{
  size_t l1 = strlen(s1), l2 = strlen(s2);
  size_t sz = (l1 + 1) * (l2 + 1) * sizeof(size_t);
  size_t w = l2 + 1;
  size_t* dpt;
  size_t i1, i2;

  if (sz / (l1 + 1) / (l2 + 1) != sizeof(size_t) ||
      (dpt = malloc(sz)) == NULL)
  {
    printf("Not enough memory\n");
    return EXIT_FAILURE;
  }

  for (i1 = 0; i1 <= l1; i1++)
    dpt[w * i1 + 0] = 0;
  for (i2 = 0; i2 <= l2; i2++)
    dpt[w * 0 + i2] = 0;

  for (i1 = 1; i1 <= l1; i1++)
    for (i2 = 1; i2 <= l2; i2++)
    {
      if (s1[l1 - i1] == s2[l2 - i2])
      {
        dpt[w * i1 + i2] = dpt[w * (i1 - 1) + (i2 - 1)] + 1;
      }
      else if (dpt[w * (i1 - 1) + i2] > dpt[w * i1 + (i2 - 1)])
      {
        dpt[w * i1 + i2] = dpt[w * (i1 - 1) + i2];
      }
      else
      {
        dpt[w * i1 + i2] = dpt[w * i1 + (i2 - 1)];
      }
    }

  i1 = l1; i2 = l2;
  for (;;)
  {
    if ((i1 > 0) && (i2 > 0) && (s1[l1 - i1] == s2[l2 - i2]))
    {
      printf("%c", s1[l1 - i1]);
      i1--; i2--; continue;
    }
    else
    {
      if (i1 > 0 &&
          (i2 == 0 || dpt[w * (i1 - 1) + i2] >= dpt[w * i1 + (i2 - 1)]))
      {
        printf("-%c", s1[l1 - i1]);
        i1--; continue;
      }
      else if (i2 > 0 &&
               (i1 == 0 || dpt[w * (i1 - 1) + i2] < dpt[w * i1 + (i2 - 1)]))
      {
        printf("+%c", s2[l2 - i2]);
        i2--; continue;
      }
    }

    break;
  }
  printf("\n");

  free(dpt);
  return EXIT_SUCCESS;
}

int main(int argc, char** argv)
{
  const char *s1, *s2;
  if (argc == 3)
  {
    s1 = argv[1]; s2 = argv[2];
  }
  else
  {
    printf("Usage:\n  lcs-diff.exe <string1> <string2>\n\n");
    s1 = "I ate apple on yesterday"; s2 = "I eat apple yesterday";
    printf("Sample comparison:\n\n  \"%s\" vs \"%s\":\n\n", s1, s2);
  }

  return lcs(s1, s2);
}

输出（ideone）：

Usage:
  lcs-diff.exe <string1> <string2>

Sample comparison:

  "I ate apple on yesterday" vs "I eat apple yesterday":

I +eat-e apple -o-n- yesterday
于 2013-04-18T21:46:15.660 回答
0

从头开始，我会这样处理这个问题（伪代码）：

String[] sarr1 = string1.split();

for (int i1 =0; i1<sarr1.length; i1++) {
  if (!string2.contains(sarr[i1]) {
    markWordRed(string1, sarr[i1]);
  }
}

String[] sarr2 = string2.split();
for (int i2 =0; i2<sarr2.length; i2++) {
  if (!string1.contains(sarr[i2]) {
    markWordRed(string2, sarr[i2]);
  }
}

从那个开始可以另外：

  • 检查单词的顺序，不仅是它们是否存在

  • 检查每个未找到的单词与第二个字符串中所有未找到的单词的相似性并显示字母差异

于 2013-04-16T09:41:31.157 回答