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

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

08.06.2013, 20:04. Показов 3372. Ответов 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
18033 / 7736 / 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
18033 / 7736 / 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
18033 / 7736 / 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
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru