Строка сравнения количества символов в том же порядке

Question

У меня есть

Str A = "abcdef"
Str B = "abcdf"

Мне нужна функция (stA, stB), которая возвращает 5 (т. Е. Количество совпавших символов), обратите внимание, что эти символы должны быть в том же порядке.

Например:

Str A = "abcdef"
Str B = "fedcba",

function(stA, stB) вернет только 1 для 'a'

Псевдокод хорош ...

ОКстати, учитывая, что все мои строки будут иметь <= 40 символов, O (n ^ 2) может быть даже лучше, чем алгоритм O (41n) .. </p>

Answer 1

Я не полностью протестировал его, но, похоже, это работает (в JavaScript) для ваших тестов:

function compare(a, b)
{
    var aChars = a.split('');
    var bChars = b.split('');

    var matches = [];
    var bStart = 0;

    for (var i=0; i < aChars.length; i++)
    {
        for (var j=bStart; j < bChars.length; j++)
        {
            if(aChars[i] == bChars[j])
            {
                matches.push(aChars[i]);
                bStart = j;
                break;
            }
        }
    }

    return matches.length;
}

compare('abcdef', 'abcdf'); // returns 5
compare('abcdef', 'fedcba'); // returns 1

В основном я начинаю с позиции 0 для строки A и позиции 0 дляСтрока B. Когда совпадение найдено, я изменяю начальную позицию для поиска строки B, чтобы она пропускала предыдущий раздел.