[закрыть]

Регистрация на сайте

Если вы уже зарегистрированы, пожалуйста войдите на сайт!
Email:
Имя (ник):
Пароль:
Повторите пароль:
  
Защита от роботов:

Плохо видно


С++ Кто-нибудь хочет размять мозг?

Borland C++ Builder. Даны две строки S1 и S2. Определить, есть ли в этих строках одинаковая подстрока из К символов. Образовать из этой подстроки новую строку.



Знаю верный ответ Найти ответ на вопрос



Ключевые слова: наибольшая общая подстрока, накрылся диск с последним С++, поиск одинаковых элементов в строках с++,

5 ответов к вопросу “С++ Кто-нибудь хочет размять мозг?”

  • ответ #0 / ответил: Служба поддержки

    • ответ #1 / ответил: hadulay
      Полезный ответ? Да (0) / Нет (0)


      По моему там стандартные функции есть, хотя и посимвольно можно не сложно замутить....Но....Влом...



      Ответить

    • ответ #2 / ответил: necessary_man
      Полезный ответ? Да (0) / Нет (0)


      ну так в чем проблема? первым циклом идем по очередному элементу первой строки и ищем его во второй строке. если нашли начинается еще один цикл сравнения подстрок, и если находим К равный символов, то копируем их во вторую строку. Усё



      Ответить

    • ответ #3 / ответил: yourfrio
      Полезный ответ? Да (0) / Нет (0)


      Метод выше ^ самый примитивный и на него в худшем случае может уйти много времени. Лучше при нахождении первого символа подстроки проверяй на последний и иди от него к началу. Так больше исключений будет и программа найдёт нужную строку гораздо быстрее. Хотя и в таком случае может быть столько же проходов в цикле, но вероятность меньше если текст адекватный. Я бы делал так.



      Ответить

    • ответ #4 / ответил: svvolkov
      Полезный ответ? Да (0) / Нет (0)


      А еще лучше все это развернуть И бежать первую строку с конца, проверяя на первый Сравнение с нулем еще никто не отменял ) Правда, визуально ты это не заметишь Совсем )



      Ответить

    • ответ #5 / ответил: egabrain
      Полезный ответ? Да (0) / Нет (0)


      Задача тривиальная: наибольшая общая подстрока, находится с использованием динамического программирования за полиномиальное время (точнее, 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;                 }             }         }     } }



      Ответить

Ответить на вопрос


Не хотите вводить проверочный код? Пройдите регистрацию!
Проверочный код:

обновить картинку

Статистика

  • © 2010-2011. Копирование материалов с сайта строго запрещено
  • Не нашли ответ? задай свой вопрос