Borland C++ Builder. Даны две строки S1 и S2. Определить, есть ли в этих строках одинаковая подстрока из К символов. Образовать из этой подстроки новую строку.
Ключевые слова: наибольшая общая подстрока, накрылся диск с последним С++, поиск одинаковых элементов в строках с++,
По моему там стандартные функции есть, хотя и посимвольно можно не сложно замутить....Но....Влом...
Ответить
ну так в чем проблема? первым циклом идем по очередному элементу первой строки и ищем его во второй строке. если нашли начинается еще один цикл сравнения подстрок, и если находим К равный символов, то копируем их во вторую строку. Усё
Ответить
Метод выше ^ самый примитивный и на него в худшем случае может уйти много времени. Лучше при нахождении первого символа подстроки проверяй на последний и иди от него к началу. Так больше исключений будет и программа найдёт нужную строку гораздо быстрее. Хотя и в таком случае может быть столько же проходов в цикле, но вероятность меньше если текст адекватный. Я бы делал так.
Ответить
А еще лучше все это развернуть И бежать первую строку с конца, проверяя на первый Сравнение с нулем еще никто не отменял ) Правда, визуально ты это не заметишь Совсем )
Ответить
Задача тривиальная: наибольшая общая подстрока, находится с использованием динамического программирования за полиномиальное время (точнее, O(n1*n2)). Адаптированный код из педивикии: void GetCommonSubstring(string & result, int max_length, const string & a, const string & b) { const int a_length = a.size(); const int b_length = b.size(); vector<vector<int>> lengths(a_length + 1, vector<int>(b_length + 1, 0)); for(int i = a_length - 1; i >= 0; i--) { for(int j = b_length - 1; j >= 0; j--) { if(a[ i ] == b[ j ]) { int length = 1 + lengths[i + 1][j + 1]; if (length < max_length) lengths[ i ][ j ] = length; else { result = a.substr(i, length); return; } } } } }
Ответить