Мы воспользуемся простой структурой данных, известной как «массив остатков». Она используется по меньшей мере с начала 70-х, хотя термин появился только в 90-х. Структура эта представляет собой массив а указателей на символы. По мере прочтения входного файла содержимое массива а инициализируется таким образом, чтобы соответствующие элементы указывали на символы входной строки:
while (ch = getchar()) != EOF a[n] = &c[n] c[n++] = ch c[n] - 0
Последний элемент массива с содержит символ \0, завершающий все строки. Элемент а[0] указывает на всю строку целиком. Следующий элемент указывает на остаток массива, начинающийся со второго символа, и так далее. Для входной строки «banana» элементам массива будут соответствовать следующие строки:
Теперь понятно, почему такой массив называется «массивомостатков».
Если длинная строка дважды входит в массив с, она окажется в двух остатках (то есть два элемента массива а будут начинаться с этой подстроки). Поэтому мы отсортируем массив а, чтобы одинаковые остатки оказались рядом (так же как анаграммы в разделе 2,4 главы 2). Массив для слова «banana» после сортировки станет таким:
а [ 0] : а а[1]¦ ana а[2] апапа а[3] ¦ banana а[4] па а[5] папа
Затем мы просканируем этот массив, сравнивая соседние элементы для выявления повторяющейся подстроки максимальной длины. В данном случае это будет слово <<апа».
Массив остатков мы отсортируем с помощью функции qsort:
qsort(a. n. sizeof(char *), pstrcmp)
Функция сравнения pstrcmp добавляет один уровень косвенности к библиотечной функции strcmp. Для вычисления количества совпадающих букв при сканировании массива используется функция com ten.
for 1 - [0. п)
if comlen(а С i]. a[i+l]) > maxlen maxlen - comlen(a[i], a[i+l]) maxi = i
pri ntf("%.*s\n” . maxien . a[maxi])
В операторе printf длина строки задается символом *, что позволяет напечатать ровно maxlen символов этой строки.
Я запустил получившуюся программу, чтобы найти самую длинную повторяющуюся подстроку в «Илиаде» Гомера (перевод Сэмюэля Батлера, 807 503 символа). Программа нашла приведенную ниже строку за 4,8 секунды:
whose sake so many of the Achaeans have died at Troy, far from their homes? Go about at once among the host, and speak fairly to them, man by man, that they draw not their ships into the sea
Опубликовал vovan666
April 17 2013 00:04:45 ·
0 Комментариев ·
4446 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
