Более быстрый алгоритм сравнения строк в C #

У меня есть два предложения, которые нужно сравнить друг с другом. Конечный результат - сколько процентов одного предложения содержится в другом, моя проблема в том, что у меня есть 100000 записей, которые нужно сравнить, скажем, еще с 10. Это 1.000.000 циклов, что в моем алгоритме очень медленное.

Это алгоритм, который я использую:

private double BreakStringsAndCheck(string s1, string s2)
{
    if (s1 == null || s2 == null || s1.Length == 0 || s2.Length == 0)
        return (double)0;
    string[] firstArray = s1.Split(' ');
    string[] secondArray = s2.Split(' ');
    if (firstArray.Length > secondArray.Length)
    {
        string[] tempArray = firstArray;
        firstArray = secondArray;
        secondArray = tempArray;
    }
    double value = 0;
    for (int i = 0; i < firstArray.Length; i++)
        for (int j = 0; j < secondArray.Length; j++)
            value += firstArray[i] == secondArray[j] ? (double)100 : (double)0;
    return findLongest ? value : value / firstArray.Length;
}

Это небольшой метод, но он не очень быстрый. По результатам моего тестирования я могу выполнить 40-60 сравнений за 1 секунду, что составляет почти 5 часов для 1 000 000 циклов.

Может ли кто-нибудь придумать другой метод или логику, которые намного быстрее этого?

Обновление:

Попробую подробнее объяснить проблему. У меня есть база данных с более чем 100 000 записей, и каждый день я вставляю и сравниваю 10-20 новых записей в этой базе данных. Эти записи представляют собой предложения от 2 до 10 слов, и мне нужно написать быстрый метод, который будет сравнивать эти новые записи с записями в базе данных, результат должен быть в процентах от того, сколько в одном предложении содержится слов из другого.

Мне нужен записи с совпадением слов более чем на 70%.

Надеюсь, теперь все понятно.