c # самый длинный образец общих слов - PullRequest
Новая
       3

c # самый длинный образец общих слов

1 голос
/ 19 февраля 2010

Я ищу самые длинные слова реализации C #. Большинство примеров, с которыми я сталкивался, сравнивают символ за символом.

другими словами, 

string1 = access
string2 = advised

должен возвращать нулевой вывод из функции

любые примеры кодов?

Ответы [ 4 ]

2 голосов
/ 19 февраля 2010

Я думаю, что эту проблему обычно называют Самая длинная общая проблема подстроки . Статья в Википедии содержит псевдокод, а реализации C # можно найти в Интернете.

1 голос
/ 01 марта 2012

Поиск различий в строках называется проблемой самой длинной общей подпоследовательности. Ниже приведено общее решение проблемы LCS, написанное на C #: 

static int[,] GetLCSDifferenceMatrix<T>(
    Collection<T> baseline,
    Collection<T> revision)
{
    int[,] matrix = new int[baseline.Count + 1, revision.Count + 1];

    for (int baselineIndex = 0; baselineIndex < baseline.Count; baselineIndex++)
    {
        for (int revisionIndex = 0; revisionIndex < revision.Count; revisionIndex++)
        {
            if (baseline[baselineIndex].Equals(revision[revisionIndex]))
            {
                matrix[baselineIndex + 1, revisionIndex + 1] =
                    matrix[baselineIndex, revisionIndex] + 1;
            }
            else
            {
                int possibilityOne = matrix[baselineIndex + 1, revisionIndex];
                int possibilityTwo = matrix[baselineIndex, revisionIndex + 1];

                matrix[baselineIndex + 1, revisionIndex + 1] =
                    Math.Max(possibilityOne, possibilityTwo);
            }
        }
    }

    return matrix;
}

Этот код дает вам матрицу «разностей», которую затем можно использовать для построения разницы из двух входов. Модульные тесты и пример использования см. http://sethflowers.com/2012/01/18/basic-diff-with-a-generic-solution-to-the-longest-common-subsequence-problem.html.

1 голос
/ 19 февраля 2010

Превращение алгоритма, который вычисляет LCS массивов символов, в алгоритм, который делает это для массивов чего-либо еще - например, массива слов - обычно довольно просто Вы пробовали это?

Если вам нужны некоторые подсказки, вот статья, которую я написал пару лет назад о том, как реализовать Longest Common Subsequence для массива слов в JScript. Вы должны быть в состоянии адаптировать его к C # без особых затруднений.

http://blogs.msdn.com/ericlippert/archive/2004/07/21/189974.aspx

1 голос
/ 19 февраля 2010

Если под словом вы подразумеваете эти буквенные вещи, отделенные от других пунктуацией, попробуйте это: 

private String longestCommonWord(String s1, String s2)
    {
        String[] seperators = new String[] { " ", ",", ".", "!", "?", ";" };
        var result = from w1 in s1.Split(seperators, StringSplitOptions.RemoveEmptyEntries)
                     where (from w2 in s2.Split(seperators, StringSplitOptions.RemoveEmptyEntries)
                            where w2 == w1
                            select w2).Count() > 0
                     orderby w1.Length descending
                     select w1;
        if (result.Count() > 0)
        {
            return result.First();
        }
        else
        {
            return null;
        }
    }

Вероятно, это не самый элегантный способ сделать это, но он работает для меня. =)

...