Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
jamesford63
0 / 0 / 0
Регистрация: 20.10.2015
Сообщений: 4
1

Поиск символов в строке C++

20.10.2015, 14:43. Просмотров 1617. Ответов 10
Метки нет (Все метки)

Помогите с задачей, буду очень благодарен
Суть задачи такова: в качестве строки вводим с клавиатуры положительное число. Длина строки не превышает 10^5.
Необходимо вывести наименьшее число не входящее в эту строку в качестве подстроки.
Т.е, например, вводим 10123456789
Должно вывести 11.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2015, 14:43
Ответы с готовыми решениями:

Поиск символов в строке
Ребят, помогите. Ломаю голову уже второй день Условие задачи заключается в...

Поиск символов в строке
Есть строка в файле txt, как организовать поиск наиболее часто повторяющегося...

Поиск символов в строке
Доброго времени суток! Помогите пожалуйста-Нужно подсчитать в строке...

Поиск символов в строке
написать прогу, которая запрашивает с клавиатуры строку, длиной 100 символов ,а...

Поиск символов в строке
задание такое: Дана строка произвольной длины. Группы символов, разделенные...

10
MaKaRoN IV
15 / 15 / 12
Регистрация: 20.04.2013
Сообщений: 64
20.10.2015, 14:54 2
Наработки есть?
0
jamesford63
0 / 0 / 0
Регистрация: 20.10.2015
Сообщений: 4
20.10.2015, 15:30  [ТС] 3
Добавлено через 1 минуту
Цитата Сообщение от MaKaRoN IV Посмотреть сообщение
Наработки есть?
Думаю можно через функцию поиска символа в строке. Берем счетчик i=0, ищем данное значение i в строке
если находим, то i++
если не находим, то выводим i
но я не совсем понимаю, как это реализовать
0
MaKaRoN IV
15 / 15 / 12
Регистрация: 20.04.2013
Сообщений: 64
20.10.2015, 15:42 4
Я бы предложил:
  1. Найти все подстроки размером 2 символа.
  2. Отсортировать их по возрастанию.
  3. Пройти по циклу найденный массив подстрок и найти пропущенную подстроку (первая такая встретившаяся строка будет решением, потому что она минимальна, так как мы идем по сортированному массиву строк).
  4. Если не нашли, то возвращаемся в пункт 1 и увеличиваем размер подстроки для поиска (станет 3,4,5... и т.д., пока не найдем решение).

Но на самом деле этот вариант может быть не производителен, надо нормально посидеть и подсчитать сложность.
Смотри простое решение ниже у Meph2015
0
Meph2015
15 / 0 / 0
Регистрация: 30.09.2015
Сообщений: 18
20.10.2015, 15:43 5
Можно так, только вместо 80 введите нужное ограничение строки:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
int main(){
    char str[80];
    cout << "Enter the number: " << endl;
    cin >> str;
    for (int i = 0;; i++){
        char number[80];
        _itoa_s(i, number, 10);
        if (!strstr(str, number)){
            cout << endl << "Min value is " << i << endl;
            break;
        }
    }
 
    system("pause");
    return 1;
}
0
Renji
2105 / 1545 / 471
Регистрация: 05.06.2014
Сообщений: 4,484
20.10.2015, 15:46 6
Цитата Сообщение от jamesford63 Посмотреть сообщение
но я не совсем понимаю, как это реализовать
Перевод числа в строку - std::to_string(1234). Поиск подстроки в строке - гуглите использование метода find у string.
0
zer0mail
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,571
Записей в блоге: 1
20.10.2015, 16:13 7
jamesford63, это олимпиадная задача?
0
jamesford63
0 / 0 / 0
Регистрация: 20.10.2015
Сообщений: 4
20.10.2015, 17:15  [ТС] 8
XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.
0
zer0mail
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,571
Записей в блоге: 1
20.10.2015, 17:37 9
Для "правильной" олимпиадной задачи простые решения "в лоб" не должны проходить по времени.
Есть реальные тестовые данные, т.к на 10123456789 не проверить?
0
jamesford63
0 / 0 / 0
Регистрация: 20.10.2015
Сообщений: 4
20.10.2015, 18:11  [ТС] 10
http://acm.timus.ru/problem.aspx?space=1&num=1769
сюда можно скинуть решение
сайт проверит
скинул сюда этот код
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
#include "iostream"
using namespace std;
#include <string>
 
int main()
{
    
    char str[100000];
    cout << "Enter the number: " << endl;
    cin >> str;
    for (int i = 1;; i++){
        char number[100000];
        _itoa_s(i, number, 10);
        if (!strstr(str, number)){
            cout << endl << "Min value is " << i << endl;
            break;
        }
    }
 
    system("pause");
    return 0;
 
}
Пишет, что ответ неправильный

Добавлено через 30 минут
А нет, извиняюсь, все работает
Просто интерфейс с сиаутами надо было убрать
0
Renji
2105 / 1545 / 471
Регистрация: 05.06.2014
Сообщений: 4,484
20.10.2015, 18:32 11
Цитата Сообщение от jamesford63 Посмотреть сообщение
А нет, извиняюсь, все работает
Работает, но каждый поиск занимает времени дофига. Ладно, посмеялись и хватит.
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
#include<iostream>
using namespace std;
int main()
{
    char str[100000];
    bool table[100000]={0};
    cin>>str;
    for(const char*start=str;*start;++start)
    {
        int value=0;
        for(const char*pos=start;*pos&&pos<start+5;++pos)
        {
            value=value*10+*pos-'0';
            table[value]=true;
        }
    }
 
    for(unsigned int i=0;i<sizeof(table);++i)
        if(!table[i])
        {
            cout<<i<<endl;
            break;
        }
    return 0;
}
1
20.10.2015, 18:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.10.2015, 18:32

Поиск четных символов в строке
вот мой код int main() { string a; getline(cin, a); for (int i = 0;...

Поиск чисел в строке символов
Прошу помочь с алгоритмом,т к сама не понимаю. Пыталась записать каждое число в...

Поиск палиндрома в строке символов
Условие задачи: 1) Задан символьный массив F(N), N&lt;=260. Найти отрезок массива...


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

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

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