高效的字符串比较

Question

我一直在尝试实现一种高效的字符串比较算法，它会根据字符的变化给出分数。

例如：

String #1: abcd  
String #2: acdb  
Initial Point: 0

在这里，字符串#2字符c将其索引从2更改为1，d将其索引从4更改为3。这两个字符(2-1=1和4-3=1)与初始点之和为2。不是家庭作业之类的，我只是不想创建一个基本的for循环来逐个比较每个字符，而是想问是否有什么有效的方法(比如散列等)。可以应用吗？

Answer 1

你把一件简单的事情搞得过于复杂了。没有比比较每个字符并在发现不同的第一个字符停止比较更有效的方法了--这基本上就是strcmp所做的。您可以做的唯一典型优化是，如果您已经知道这两个字符串的长度(当您使用std::string或其他计数字符串时会发生这种情况)，如果两个字符串的长度不同，则立即确定它们是否相等。

Answer 2

听起来你真正想要的是像Levenshtein distance这样的东西(但不完全是这样)。这是第一次裁剪。

它所做的就是遍历a的所有可能的重新安排的博弈树，看看它们是否与b匹配。它将每个重新安排的成本关联到一个递减的预算。

外部循环首先使用预算0进行遍历，因此只允许精确匹配。

如果没有成功，那么它的预算为1，找到所有只包含一次重排的匹配项。

如果没有成功，那么它的预算是2，依此类推。

当它匹配时，它保存一个整数增量数组，告诉a的每个元素被交换了多远。每当它成功时，它就会打印出增量数组，这是您为获得匹配而进行的交换操作的记录。

void walk(char* a, char* b, int* delta, int budget, int& nSuccess){
  delta[0] = 0;
  if (budget < 0) return;
  if (a[0] == '\0' && b[0] == '\0'){ // end of both strings
    nSuccess++;
    // print out the deltas
    return;
  }
  if (a[0] == '\0') return; // excess chars in b
  if (b[0] == '\0') return; // excess chars in a
  if (a[0] == b[0]){ // first chars are equal, move to next
    walk(a+1, b+1, delta+1, budget, nSuccess);
    return;
  }
  for (int i = 1; a[i] != '\0'; i++){
    delta[0] = i;
    swap(a[0], a[i]);
    if (a[0] == b[0]){
      walk(a+1, b+1, delta+1, budget-1, nSuccess);
    }
    swap(a[0], a[i]);
    delta[0] = 0;
  }
}

void top(char* a, char* b){
  int nSuccess = 0;
  int delta[512];
  for (int budget = 0; nSuccess==0; budget++){
    walk(a, b, budget, delta, nSuccess);
  }
}

该算法的性能是N的指数，其中N是使字符串匹配所需的最小重排次数。因此，在验证了每个字符串具有相同数量的每个字符之前，可能不应该使用它，并且只有在需要查看重排记录时才使用它。