Заказанный последовательный текст, соответствующий

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 

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

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

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

Answer 1

Я пришел к выводу, что ваш «счет» представляет собой крайнее левое положение символа, в котором строки отличались.

Не обращайте внимания на «mapreduce», простой Jane Java может сделать это очень легко.

**

общественного ИНТ счет (String string1, String строка2) {
        символ sbuf1 [] = string1.toCharArray();
        char sbuf2 [] = string2.toCharArray();

        int complen = sbuf1.length;

        если (sbuf2.length < complen) {
                complen = sbuf2.length;
       }
        для ( INT I = 0; я < complen, я ++) {
                если (sbuf1 [я]!= sbuf2 [я]) {
                        возвращение я;
               }
       }
возврата -1; // не указывает на несоответствие обнаруженных до того одна строка исчерпала
}

**