Эффективное сравнение строк

Question

Я пытался реализовать эффективный алгоритм сравнения строк, который будет давать точки в соответствии с изменениями символов.

Например:

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

Здесь, строка # 2, символ cизменил его индекс с 2 на 1, а d изменил свой индекс с 4 на 3. Оба (2-1=1 и 4-3=1) прибавляют до 2 баллов к начальной точке.Не домашнее задание или что-то еще, я просто не хотел создавать базовый цикл для сравнения каждого символа по одному и хотел спросить, можно ли применить какой-нибудь эффективный метод (например, хеширование и т. Д.)?

Answer 1

Вы слишком усложняете простую вещь. Вы не можете добиться большей эффективности, чем сравнение каждого символа и остановка сравнения на первом символе, который вы считаете отличным, - именно это и делает strcmp. Единственная типичная оптимизация, которую вы можете сделать, - это если вы уже знаете длину двух строк (как это происходит, когда вы используете std::string или другие подсчитанные строки), чтобы сразу определить их неравно, если эти две длины различаются.

Answer 2

Похоже, что вы действительно хотите, это что-то вроде расстояния Левенштейна (но не совсем так). Вот первый разрез.

Что нужно сделать, это пройтись по дереву игр со всеми возможными перестановками a , чтобы увидеть, соответствуют ли они b . Он связывает стоимость с каждой перестановкой, выраженную в уменьшении бюджета .

Сначала идет внешний цикл с бюджетом 0, поэтому допускается только точное совпадение.

Если он не увенчался успехом, он обходится с бюджетом 1, находя все совпадения, содержащие только одну перестановку.

Если это не принесло успеха, тогда он идет с бюджетом 2 и т. Д.

При совпадении он хранит массив целых чисел delta , указывающий, как далеко каждый элемент из 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 - минимальное количество перестановок, необходимое для согласования строк. Так что, вероятно, его не следует использовать до тех пор, пока вы не убедитесь, что каждая строка имеет одинаковое количество каждого символа, и используйте его, только если вам нужна эта запись о перестановках.