Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/14: Рейтинг темы: голосов - 14, средняя оценка - 5.00
MayaNash
1291 / 460 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
1

Поиск наиболее часто встречающейся подстроки в строке

31.10.2014, 15:05. Просмотров 2715. Ответов 57
Метки нет (Все метки)

Прошло уже немало лет с тех пор, как Лич Сандро ушёл на заслуженный отдых. Иногда по вечерам, когда ему становится совсем тоскливо, он берёт в руки книгу, которую ему подарили воспитанники-маги по случаю выхода на пенсию.
Вот и сейчас великий маг взял с полки книгу и углубился в чтение. В одной из глав рассказывалось про знаменитое открытие Сандро — много лет назад он придумал универсальное заклинание. Оказалось, что любая его подстрока (последовательность подряд идущих букв) тоже является заклинанием, а сила любого заклинания равна количеству раз, которое это заклинание встречается в универсальном (например, строка «ue» встречается в строке «queue» дважды, а строка «aba» в строке «abababa» — трижды).
Сейчас у Сандро много свободного времени, и он решил найти самое сильное заклинание. Помогите ему в этом.

Исходные данные
Единственная строка содержит универсальное заклинание, которое открыл Сандро. Заклинание — непустая строка из строчных латинских букв длиной не более 50.

Результат
Выведите любое из заклинаний, обладающих, по мнению Сандро, наибольшей силой.

Пример
Код
исходные данные   результат
tebidohtebidoh    tebidoh
На какой подстроке ответ может быть неверный? Программа неправильно отвечает на второй тест...
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
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string str, podstr, maxpodstr;
    // строка, текущая подстрока, подстр., которая встречается максимальное количество раз
    int maxk = 0, k, pos; // количество maxpodstr, количество текущей podstr, последняя найденная позиция podstr
    cin >> str;
    for (int i = 0; i < str.length(); i++) // с первого по последний символ
        for (int j = 1; j < str.length()-i; j++) // берем с одного до конца строки символов
        { // и смотрим сколько раз эта подстрока встретится
            podstr = str.substr(i, j);
            k = (str.find(podstr, 0) == 0? 1 : 0), pos = 0; // если на нулевой позиции есть эта подстрока,
                                                            // то одно вхождение уже есть
            do
            {
                pos = str.find(podstr, pos+1); // находим следующее вхождение (при pos==0 ищем со второго символа)
                if (pos != string::npos) // если нашли, увеличиваем количество вхождений, иначе выходим из цикла
                    k++;
                else
                    break;
            }
            while (true);
            if (k > maxk) // если нашли чаще встречающуюся подстроку
            {
                maxk = k; // запоминаем ее
                maxpodstr = podstr;
            }
        };
    cout << maxpodstr;
    return 0;
}
Добавлено через 1 час 27 минут
актуально
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2014, 15:05
Ответы с готовыми решениями:

Пользуясь указателями найти слова с наиболее часто встречающейся длиной
Заданный текст длиной более 10 слов распечатать по строкам, понимая под строкой...

Поиск наиболее часто встречающихся слов в файле
Дан символьный файл f, содержащий произвольный текст длиной более 5000 слов....

Найти и вывести на консоль символы, наиболее часто встречающиеся в заданной строке
В тексте найти и напечатать символы, встречающиеся наиболее часто. Помогите !

Найти наиболее часто встречающуюся букву и также вывести на экран в отдельной строке
Помогите с прогой. : В произвольном тексте (взятом из файла), содержащем не...

Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ
нужно найти в строке пару символов, которые повторяются чаще всех и заменить их...

57
CheshireCat
Эксперт С++
2912 / 1261 / 114
Регистрация: 27.05.2008
Сообщений: 3,464
31.10.2014, 15:25 2
Цитата Сообщение от Керра Посмотреть сообщение
Оказалось, что любая его подстрока (последовательность подряд идущих букв) тоже является заклинанием, а сила любого заклинания равна количеству раз, которое это заклинание встречается в универсальном (например, строка «ue» встречается в строке «queue» дважды, а строка «aba» в строке «abababa» — трижды).
Фигня-с.
Самое сильное заклинание в строке "abababa" - это "а".
0
MayaNash
1291 / 460 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
31.10.2014, 15:27  [ТС] 3
CheshireCat, это говорит о том, что последовательность может быть длиной минимум 2. Я пробовала и минимум 1 и минимум 2 - все равно на втором тесте неправильный ответ.
0
DiffEreD
1442 / 779 / 257
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
31.10.2014, 18:36 4
Вот что у меня получилось:
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
std::vector<std::string> f(const std::string& s) {
   if (s.empty() || s.size() == 2) return {s};
 
   std::map<std::string, size_t> map;
   for (auto beg = s.begin(), end = s.end(); beg != end; ++beg) {
      for (size_t i = 2; i <= std::distance(beg, end); ++i)
         ++map[{beg, beg+i}];
   }
 
   //for (auto &p : map)
      //std::cout << p.first << " = " << p.second << "\n";
 
   using pair = std::pair<std::string, size_t>;
   auto max = *std::max_element(map.begin(), map.end(),
                              [](const pair& p1, const pair& p2)
   {return p1.second < p2.second;});
 
   std::vector<std::string> results;
   std::for_each(map.begin(), map.end(), [&](const pair& p)
   {
      if (p.second == max.second) results.push_back(p.first);
   });
 
   return results;
}
 
int main()
{
   auto  res = f("tebidohtebidoh");
   for (auto &s : res)
      std::cout << s << "\n";
}
0
MayaNash
1291 / 460 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
31.10.2014, 18:37  [ТС] 5
DiffEreD, не всем нужны просто готовые решения))
0
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 18:47 6
Цитата Сообщение от Керра Посмотреть сообщение
Программа неправильно отвечает на второй тест...
Какой второй тест? Где он?
0
MayaNash
1291 / 460 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
31.10.2014, 18:49  [ТС] 7
а, забыла ссылочку... http://acm.timus.ru/problem.aspx?space=1&num=1723

Добавлено через 42 секунды
не работает ссылочка... 1723 задача на acm.timus.ru, в общем
0
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 19:05 8
Керра, а ты как свой алгоритм проверял(а)?
У меня он на "tebidohtebidoh" выводит "t".
На "queue" выводит "u".
На "abababa" выводит "a".

Странно что он вообще прошел первый тест.
0
MayaNash
1291 / 460 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
31.10.2014, 19:06  [ТС] 9
castaway, а, это я сюда выложила с минимумом один символ. В 12-й строке замените на j = 2. Но все равно не проходит второй тест.
0
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 19:07 10
Керра, а ты как свой алгоритм проверял(а)?
У меня он на "tebidohtebidoh" выводит "t".
На "queue" выводит "u".
На "abababa" выводит "a".

Странно что он вообще прошел первый тест.
0
MayaNash
1291 / 460 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
31.10.2014, 19:07  [ТС] 11
вообще, там нет уточнения насчет количества символов в подстроке
0
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 20:07 12

Не по теме:

Пардон. Проблемы с интернетом.



Добавлено через 51 минуту
Мало того, что придумать алгоритм довольно сложно, разобраться в твоём ещё сложнее.
В общем, у меня получилось что-то на подобие твоего, попробуй на основании него найти ошибки в своём.
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
#include <iostream>
#include <string>
 
using namespace std;
 
string find_spell( string spell ) {
 
    unsigned cnt_spell = 0;
    string sub_spell;
 
    unsigned size = spell.size();
    for ( unsigned i = 0; i < size; ++i ) {
        for ( unsigned j = 1; j <= size - i; ++j ) {
            string sub = spell.substr( i, j );
 
            unsigned cnt = 0;
            for ( unsigned k = i + 1; k <= size - sub.size(); ++k ) {
                std::string::size_type n = spell.find( sub, k );
                if ( n != string::npos ) ++cnt;
            }
 
            if ( cnt > cnt_spell ) {
                sub_spell = sub;
                cnt_spell = cnt;
            } else if ( cnt == cnt_spell && sub.size() > sub_spell.size() ) {
                sub_spell = sub;
                cnt_spell = cnt;
            }
        }
    }
    return sub_spell;
}
 
int main()
{
    cout << "tebidohtebidoh - " << find_spell( "tebidohtebidoh" ) << endl;
    cout << "queue - " << find_spell( "queue" ) << endl;
    cout << "abababa - " << find_spell( "abababa" ) << endl;
    return 0;
}
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
31.10.2014, 20:38 13
Лучший ответ Сообщение было отмечено MayaNash как решение

Решение

Керра, вбей строку из 1 символа. работает?

Добавлено через 6 минут
и сразу еще одно решение(оно прошло).

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
 
using namespace std;
 
int cnt[256];
 
int main(){
 
    string s;
    getline(cin, s);
    int n = s.length();
    for(int i = 0; i < n; i++)
        cnt[s[i]]++;
 
    int mx = 0;
    for(int i = 0; i < 256; i++)
        if(cnt[i] > cnt[mx])
            mx = i;
 
    cout << char(mx) << endl;
 
    return 0;
}
1
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 20:52 14
SlavaSSU, как оно могло пройти, если требуется вывести "заклинание", а у тебя выводится один символ?
Или условие вывода в первом посте ошибочные?

Не по теме:

Сам на тимус не заходил и не смотрел.

0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
31.10.2014, 20:53 15
castaway, 1 символ не является подстрокой?

нетрудно сообразить что всегда найдется ответ состоящий из подстроки длиной 1.
1
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 20:54 16
SlavaSSU, как оно могло пройти, если требуется вывести "заклинание", а у тебя выводится один символ?
Или условие вывода в первом посте ошибочные?

Не по теме:

Сам на тимус не заходил и не смотрел.

0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
31.10.2014, 20:58 17
castaway, ?

дана строка длиной до 50. Вывести любую из ее подстрок, количество вхождений которых максимально.
Найдем самый частый символ и выведем его. Чем это противоречит условию?
1
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 21:04 18
Цитата Сообщение от SlavaSSU Посмотреть сообщение
castaway, 1 символ не является подстрокой?
Является. Только он не является самым "сильным" заклинанием.
В случае с "queue" - самым "сильным" заклинанием будет "ue", а не "u". Вроде это не трудно сообразить!?

Добавлено через 4 минуты

Не по теме:

SlavaSSU, ты прав, я не верно трактовал условие. Просто ТС ввела нас в заблуждение. Отдаю должное.



Добавлено через 14 секунд

Не по теме:

SlavaSSU, ты прав, я не верно трактовал условие. Просто ТС ввела нас в заблуждение. Отдаю должное.

0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
31.10.2014, 21:05 19
castaway, queue

подстроки u, e, ue - встречаются по 2 раза, выведем любое.

самое сильное заклинание то, которое ВСТРЕЧАЕТСЯ НАИБОЛЬШЕЕ ЧИСЛО РАЗ. ЕСЛИ ТАКИХ НЕСКОЛЬКО, ТО ВЫВЕДИТЕ ЛЮБОЕ!!!
0
castaway
Эксперт С++
4934 / 3039 / 455
Регистрация: 10.11.2010
Сообщений: 11,119
Записей в блоге: 10
Завершенные тесты: 1
31.10.2014, 21:13 20
SlavaSSU, не психуй. Читай выше.
0
31.10.2014, 21:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2014, 21:13

Найти наболее часто встречающейся год рождения в массиве - С++
Вот код, в котором я открываю файл и записываю из него значения в массив....

Поиск подстроки в строке
Добрый день. Ошибка в программе. Первый раз ищет отлично, потом постоянно...

Поиск подстроки в строке
Всем доброе утро! Задачка звучит так - найти самую длинную подстроку в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru