Какой алгоритм использовать для нахождения повторяющихся слов в строке?
Задача поставлена странно, во первых ни в одном языке нет миллиона слов, а используется в среднем от 3 до 10 тыс. То есть задача для миллиона в корне неверна. В любом случае как минимум 1 проход потребуется в любом случае, я бы сделал так.
1. Создание dictionary слов и их количества
2. Проход по очереди всех слов
3. Поиск текущего слова в списке, если его там нет добавляем в список и количество выставляем в 1, если есть +1 к количеству
В итоге получаем 1 проход по всему тексту и обращение по индексу к dictionary, которое стоит относительно дешево, намного дешевле перебора всего списка.
Похожий подход применял для анализа текстов, в итоге для 20 книг ~500 стр каждая уходило около 3-5 секунд.
Для C# это выглядит так
я извиняюсь, а (\w+) \1
чем не подходит?
слова идут не подряд?
тогда строку  в массив, сорт и ..