Задача: Для двух заданных строк символов найти самую длинную общую подстроку. Пробелы и знаки препинания игнорировать, строчные и прописные буквы считать неразличимыми. Например, строки: «Дай вилку! Бок севрюжий кончается» и «Чемпионский кубок достался не нам» содержат общую подстроку «кубок».
| Строка а | Строка 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++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <string> #include <cctype> using namespace std; int main() { string a, b; getline(cin, a); getline(cin, b); string a2, b2; for(auto i: a){ if(isalpha(i)){ a2.push_back(tolower(i)); //Избавляемся от всех знаков кроме букв и понижаем регистр. } } for(auto i: b){ if(isalpha(i)){ b2.push_back(tolower(i)); } } if(a2==b2){ cout << a2; //Если строки равны, сразу возвращаем значение одной из них. return 0; } string c; for(unsigned int i=0; i<a2.size(); i++){ //Сравниваем символы в строках. for(unsigned int j=0; j<b2.size(); j++){ if(a2[i]==b2[j]){ c.push_back(a2[i]); for(unsigned int k=i+1, t=j+1; (k<a2.size())&&(t<b2.size()); k++, t++){ if(a2[k]==b2[t]){ c.push_back(a2[k]); //Те, которые совпали, записываем в новую строку. } else { break; } } c.push_back(' '); } } } unsigned int r=0, max=0; //В получившейся строке считаем, сколько букв в самом большом слове. string c2, maxstr; for(unsigned int i=0; i<c.size(); i++){ if(c[i]!=' '){ r++; } else { if(r>max){ max=r; } r=0; } } for(unsigned int i=0; i<c.size(); i++){ //Ищем слова такой же длины и записываем их в строку для вывода черех пробел. if(c[i]!=' '){ c2.push_back(c[i]); } else { if(c2.size()==max){ for(auto j: c2){ maxstr.push_back(j); } maxstr.push_back(' '); } c2.clear(); } } cout << maxstr; return 0; } |
Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { Scanner in = new Scanner(System.in); String a, b; a = in.nextLine(); b = in.nextLine(); String a2 = new String(); String b2 = new String(); char ch; for(int i=0; i<a.length(); i++){ ch = a.charAt(i); if(Character.isLetter(ch)){ a2+=Character.toLowerCase(ch); //Избавляемся от всех знаков кроме букв и понижаем регистр. } } for(int i=0; i<b.length(); i++){ ch = b.charAt(i); if(Character.isLetter(ch)){ b2+=Character.toLowerCase(ch); //Избавляемся от всех знаков кроме букв и понижаем регистр. } } if(a2==b2){ System.out.println(a2);//Если строки равны, сразу возвращаем значение одной из них. } else { String c = new String(); for(int i=0; i<a2.length(); i++){ //Сравниваем символы в строках. for(int j=0; j<b2.length(); j++){ if(a2.charAt(i)==b2.charAt(j)){ c+=a2.charAt(i); for(int k=i+1, t=j+1; (k<a2.length())&&(t<b2.length()); k++, t++){ if(a2.charAt(k)==b2.charAt(t)){ c+=a2.charAt(k);//Те, которые совпали, записываем в новую строку. } else { break; } } c+=' '; } } } int r=0, max=0; //В получившейся строке считаем, сколько букв в самом большом слове. String c2 = new String(); String maxstr = new String(); for(int i=0; i<c.length(); i++){ if(c.charAt(i)!=' '){ r++; } else { if(r>max){ max=r; } r=0; } } for(int i=0; i<c.length(); i++){ //Ищем слова такой же длины и записываем их в строку для вывода черех пробел. if(c.charAt(i)!=' '){ c2+=c.charAt(i); } else { if(c2.length()==max){ for(int j=0; j<c2.length(); j++){ maxstr+=c2.charAt(j); } maxstr+=' '; } c2 = new String(); } } System.out.println(maxstr); } } } |
Даны строки [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] считаем, сколько букв в самой длинной подстроке. А после этого ищем слова такой длины и записываем их в строку для вывода через пробел.
Отлично, сложная задача сделана без единой ошибки (ну по крайней мере я не нашел). Засчитано, 10 баллов. Можете сделать еще через c-строки (массивы символов) — относительно несложно переделать и получить еще 10 баллов.
Правда, Вы несколько увлеклись успешным для этой задачи приемом с посимвольным добавлением при помощи push_back и использовали его даже для конкатенации строк — чрезмерное усложнение, строки 59-62 можно заменить на простую конструкцию maxstr+=c2+' ';
И еще один момент — касающийся оптимизации алгоритма и программы — у Вас строка c очень сильно разрастается в размерах. См. например http://ideone.com/7jDHit.
К сожалению, использован не самый эффективный метод — конкатенация строк, а не StringBuilder, StringBuffer. 8 баллов.