Ю12.43

Задача: Для двух заданных строк символов найти самую длинную общую подстроку. Пробелы и знаки препинания игнорировать, строчные и прописные буквы считать неразличимыми. Например, строки: «Дай вилку! Бок севрюжий кончается» и «Чемпионский кубок достался не нам» содержат общую подстроку «кубок».

Строка а Строка b  Результат Комментарий
Q_+wer ty q!w ert) q qwert Тест пройден
`Curiouser and curiouser!’ cried Alice (she was so much surprised, that for the moment she quite forgot how to speak good English); `now I’m opening out like the largest telescope that ever was! Good-bye, feet!’ (for when she looked down at her feet, they seemed to be almost out of sight, they were getting so far off). `Oh, my poor little feet, I wonder who will put on your shoes and stockings for you now, dears?

 

tfor good Тест пройден
Qwe^r ty qwE r!ty qwerty  Тест пройден

C++:

Java:

Даны строки [latex]a[/latex] и [latex]b[/latex]. Сначала переписываем их в строки [latex]a2[/latex] и [latex]b2[/latex], при этом избавляясь от всех символов, кроме букв, и понижая их регистр.

Чтобы выделить все совпадающие комбинации букв, сравниваем каждый символ из [latex]a2[/latex] подряд со всеми символами из  [latex]b2[/latex]. Когда находим одинаковые буквы, проверяем уже следующий символ в [latex]a2[/latex] и в  [latex]b2[/latex]. Все общие подстроки записываем в строку  [latex]c[/latex] через пробел.

Так как в строках может быть несколько общих подстрок наибольшей длины, сначала в строке [latex]c[/latex] считаем, сколько букв в самой длинной подстроке. А после этого ищем слова такой длины и записываем их в строку для вывода через пробел.

Задача на Ideone:
C++
Java

Related Images:

2 thoughts on “Ю12.43

  1. Отлично, сложная задача сделана без единой ошибки (ну по крайней мере я не нашел). Засчитано, 10 баллов. Можете сделать еще через c-строки (массивы символов) — относительно несложно переделать и получить еще 10 баллов.

    Правда, Вы несколько увлеклись успешным для этой задачи приемом с посимвольным добавлением при помощи push_back и использовали его даже для конкатенации строк — чрезмерное усложнение, строки 59-62 можно заменить на простую конструкцию maxstr+=c2+' ';

    И еще один момент — касающийся оптимизации алгоритма и программы — у Вас строка c очень сильно разрастается в размерах. См. например http://ideone.com/7jDHit.

Добавить комментарий