Упорядоченное последовательное сопоставление текста

Question

Я хочу сопоставить строки и получить оценку следующим образом,

   string 1: 4556677, string 2: 2556677, score: 0
   string 1: 123345873009, string 2: 123345873112, score: 9
   string 1: 22334567, string 2: 22334500, score: 6

Таким образом, оценка представляет общие первые n цифр слева направо.

У меня есть список из 100K строки 1 и 30M строки 2, я хотел бы отфильтровать все пары (строки 1 и 2) с оценкой больше, чем "х".

Существует ли алгоритм для выполнения этой задачи вместо последовательного сопоставления с применением жестокой силы? У меня есть таблицы, хранящиеся в apache hive /hbase, и я хотел бы реализовать подход либо в spark, либо в java mapreduce. Буду признателен за любую оказанную помощь.

Answer 1

Я делаю вывод, что ваш "счет" представляет крайнюю левую позицию символа, в которой строки различались.

Не берите в голову "mapreduce", простая Джейн Ява может сделать это очень легко.

**

public int score (String string1, String string2) {
char sbuf1 [] = string1.toCharArray ();
char sbuf2 [] = string2.toCharArray ();

int completen = sbuf1.length;

if (sbuf2.length compn = sbuf2.length;
}
for (int i = 0; i if( sbuf1[ i ]!= sbuf2[ i ]) {
вернуть я;
}
}
возврат -1; // указывает, что несоответствие не обнаружено до исчерпания одной строки
}

**