Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/15: Рейтинг темы: голосов - 15, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 22

Найти в тексте все вхождения данного образца

08.06.2013, 20:04. Показов 3294. Ответов 17
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Буду рад любой помощи
вообще непонятна сама организация поиска, помогите пожалуйста
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
08.06.2013, 20:04
Ответы с готовыми решениями:

В данном тексте подсчитать все вхождения подстроки «abc» и удалить их
Задача программы такая: "В данном тексте подсчитать все вхождения подстроки «abc» и удалить их. Вывести два варианта результата: с...

Написать программу, которая удаляет из данного набора символов все вхождения символов S и s
Написать программу, которая получает от пользователя набор символов, исключая пропуск, и удаляет из этого набора все вхождения символов S и...

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

17
 Аватар для dr.curse
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
08.06.2013, 20:14
Novicheki, http://e-maxx.ru/algo/prefix_function
http://e-maxx.ru/algo/rabin_karp
1
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 22
08.06.2013, 23:09  [ТС]
Неправильно работает, в чем может быть ошибка?
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
using namespace std;
int main(){
    setlocale(LC_ALL, "Russian");
    int t;
        double timeStart, timeEnd, resultTime;
    string src, sub;
    cout<<"Vvetite stroku";
    cin>>src;
    cout<<"Vvedite vhoshdenie";
    cin>>sub;
    cout << "Колличество ядер: ";
    cin >> t;
    omp_set_num_threads(t);
        int start = 0;
        int count = 0;
        int pos = 0;
     timeStart = omp_get_wtime();
    #pragma omp parallel default(none) shared(start,count,pos, sub, src)
    {  
        #pragma omp for ordered reduction(+:count)
            for(;;){
        pos = src.find(sub.c_str(),start);
        if (pos != -1){
            start = pos + sub.size();
            count++;
        } 
        else break;
    }
    }
       cout <<"y="<<count<<endl;
    timeEnd = omp_get_wtime ();
    resultTime =timeEnd-timeStart;
    cout<<"t="<< resultTime <<endl;              
    return 0;
    _getch();
 
    return count;
}
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
09.06.2013, 00:41
Цитата Сообщение от Novicheki Посмотреть сообщение
все вхождения данного образца
Aho–Corasick string matching algorithm
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 00:59
Novicheki, если без алгоритмов, которые представлены в постах 2 и 4, то можно так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
 
int main()
{
    std::string str = "Hello world! abc...abc...abc...ab";
    std::string match_seq = "abc";
    unsigned match_count = 0;
    size_t pos;
    while ( (pos = str.find(match_seq, ++pos)) != std::string::npos )
        ++match_count;
    std::cout << match_count;
    return 0;
}
2
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18030 / 7733 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
09.06.2013, 03:06
Olivеr, инициализировать так?
C++
1
size_t pos = -1;
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 15:14
Dragokas, в данном случае инициализировать не обязательно, ведь в цикле есть присвоение результата функции string::find() которая в любом случае вернет или конкретную позицию или string::npos (то, что вы написали). А если все таки инициализировать, то лучше так:
C++
1
size_t pos = static_cast<size_t>(-1);
0
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18030 / 7733 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
09.06.2013, 16:01
Olivеr, присвоение есть, но сначала происходит инкремент ++pos, а начальное значение не присвоено.
Мой VS 2012 на это ругается.
1
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
09.06.2013, 16:04
Olivеr, ищет то от ++pos, которое на момент поиска еще не очевидно, т.е. pos ни к чем не приравнивалось и может быть чем угодно
0
 Аватар для dr.curse
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
09.06.2013, 16:05
Цитата Сообщение от Olivеr Посмотреть сообщение
C++
1
pos = str.find(match_seq, ++pos)
насколько я знаю тут undefined behavior поэтому и разные копиляторы реагируют по разнумо
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 16:07
Да, все правильно, не заметил. GCC инициализировала нулем. С
C++
1
size_t pos = -1
и строкой "abcHello world! abc...abc...abc...ab" работает?
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
09.06.2013, 16:52
Olivеr, мб все-таки int pos = -1?
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 17:01
MrGluck, в int может не поместится. size_t pos = -1, после ++pos получаем ноль. или же long long pos = -1
0
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18030 / 7733 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
09.06.2013, 17:30
std::string::npos = 4 294 967 295
а на x64 - также?

unsigned int - от 0 до 4 294 967 295

Его по идее тоже можно использовать здесь. Правда, такой красивой конструкции уже не получится.
А экономии памяти все равно не будет (оба 4 байт в х32 режиме).

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
 
int main()
{
    std::string str = "abc Hello world! abc...abc...abc...ab";
    std::string match_seq = "abc";
    unsigned match_count = 0;
    unsigned int pos = 0;
    std::cout << sizeof(pos) << std::endl;
    std::cout << std::string::npos << std::endl;
    while ( (pos = str.find(match_seq, pos)) != std::string::npos )
    {
        ++match_count;
        ++pos;
    }
    std::cout << match_count;
    system("pause>nul");
    return 0;
}



Тут пишут size_t - беззнаковый тип, а как же -1 http://www.viva64.com/ru/a/0050/
Какой диапазон чисел он принимает, не могу найти?

Если можно вопрос - что это за тип:
C++
unsigned match_count = 0;
Добавлено через 2 минуты
Цитата Сообщение от Olivеr Посмотреть сообщение
(переполнение)
ааа... понял, при -1 окажется по другую сторону стека.
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 17:35
Цитата Сообщение от Dragokas Посмотреть сообщение
std::string::npos = 4 294 967 295
а на x64 - также?
На x64 - 18446744073709551615, то есть 2 в степени 64 (максимальное значение беззнакового типа size_t)

Цитата Сообщение от Dragokas Посмотреть сообщение
А экономии памяти все равно не будет (оба 4 байт в х32 режиме).
дело не в экономии памяти, а в том, что текст может быть ну очеень длинным

Цитата Сообщение от Dragokas Посмотреть сообщение
Тут пишут size_t - беззнаковый тип, а как же -1
Запишите минус один в дополнительном коде и поймете

Цитата Сообщение от Dragokas Посмотреть сообщение
Если можно вопрос - что это за тип:
Беззнаковое целое. От 0 до 4294967295

Добавлено через 3 минуты
Цитата Сообщение от Dragokas Посмотреть сообщение
Цитата Сообщение от Olivеr
(переполнение)
вот по поводу переполнения я не уверен. Забил в МАСМ код:
Assembler
1
2
    mov eax, 4294967295d
    inc eax
Флаг переполнения в итоге не поднялся, но eax стан равен нулю.

А вот и почему:
OF — флаг переполнения. Этот флаг устанавливается в 1, если результат предыдущей арифметической операции над числами со знаком выходит за допустимые для них пределы. Например, если при сложении двух положительных чисел получается число со старшим битом, равным единице (то есть отрицательное) и наоборот.
Т.е. только для знаковых
1
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
09.06.2013, 18:19
Цитата Сообщение от Olivеr Посмотреть сообщение
в int может не поместится
всего лишь в 2 раза меньше диапазон, чем у size_t.
Это ничто по сравнению с записью в unsigned отрицательных чисел.
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 18:27
Цитата Сообщение от MrGluck Посмотреть сообщение
всего лишь в 2 раза меньше диапазон, чем у size_t.
На x32 - согласен, но на x64 int меньше size_t в 2^33 раз
Цитата Сообщение от MrGluck Посмотреть сообщение
Это ничто по сравнению с записью в unsigned отрицательных чисел.
Почему? Даже в реализации std::string npos записали так:
C++
1
2
3
4
5
template<typename _CharT, typename _Traits, typename _Alloc>
class basic_string{
public:
     static const size_type    npos = static_cast<size_type>(-1);
...
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
09.06.2013, 18:35
Полез в стандарт:
4.7.2
If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source
integer (modulo 2n where n is the number of bits used to represent the unsigned type). [ Note: In a two’s
complement representation, this conversion is conceptual and there is no change in the bit pattern (if there
is no truncation). —end note ]
Т.е. таки да, можно, но по моему использовать int все же в этой задачке очевидней и вариант того, что вылезем за нужный диапазон ну очень мал. В конце концов, long long.

Добавлено через 1 минуту
Кстати, насколько или во сколько size_t должен превосходить int стандартом не описано (вернее написано, что кол-во байт под них может быть любое), лишь говорится, что unsigned ... должен быть больше чем signed ...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
09.06.2013, 18:35
Помогаю со студенческими работами здесь

Найти все вхождения строки s в t
Требуется написать программу, которая выводить на экран идексы всех вхождений строки s в строку t: abababababa aba 0 2 4 6 8 ...

Найти все вхождения подстроки в строку
Задача: Найти все вхождения подстроки в строку. На языке C++

Найти все вхождения строки Т в строке S
Найти все вхождения строки Т в строке S Помогите пожалуйста! И если можно на языке Си!!!

Заменить все первые левые вхождения символа “a” на 00, а все правые вхождения символа “a” на 11
Заменить все первые левые вхождения символа “a” на 00, а все правые вхождения символа “a” на 11, остальные без изменений

Найти все вхождения подстроки в строку и удалить их из исходной строки
Ввести с экрана строку и подстроку. Найти все вхождения подстроки в строку и удалить их из исходной строки.


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru