Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Novicheki
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 22
#1

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

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

Буду рад любой помощи
вообще непонятна сама организация поиска, помогите пожалуйста
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2013, 20:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти в тексте все вхождения данного образца (C++):

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

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

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

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

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

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

17
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
08.06.2013, 20:14 #2
Novicheki, http://e-maxx.ru/algo/prefix_function
http://e-maxx.ru/algo/rabin_karp
1
Novicheki
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 22
08.06.2013, 23:09  [ТС] #3
Неправильно работает, в чем может быть ошибка?
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
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
09.06.2013, 00:41 #4
Цитата Сообщение от Novicheki Посмотреть сообщение
все вхождения данного образца
Aho–Corasick string matching algorithm
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 00:59 #5
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
Dragokas
Эксперт WindowsАвтор FAQ
15998 / 6815 / 821
Регистрация: 25.12.2011
Сообщений: 10,555
Записей в блоге: 16
09.06.2013, 03:06 #6
Olivеr, инициализировать так?
C++
1
size_t pos = -1;
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 15:14 #7
Dragokas, в данном случае инициализировать не обязательно, ведь в цикле есть присвоение результата функции string::find() которая в любом случае вернет или конкретную позицию или string::npos (то, что вы написали). А если все таки инициализировать, то лучше так:
C++
1
size_t pos = static_cast<size_t>(-1);
0
Dragokas
Эксперт WindowsАвтор FAQ
15998 / 6815 / 821
Регистрация: 25.12.2011
Сообщений: 10,555
Записей в блоге: 16
09.06.2013, 16:01 #8
Olivеr, присвоение есть, но сначала происходит инкремент ++pos, а начальное значение не присвоено.
Мой VS 2012 на это ругается.
1
MrGluck
Модератор
Эксперт CЭксперт С++
7423 / 4538 / 673
Регистрация: 29.11.2010
Сообщений: 12,319
09.06.2013, 16:04 #9
Olivеr, ищет то от ++pos, которое на момент поиска еще не очевидно, т.е. pos ни к чем не приравнивалось и может быть чем угодно
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.06.2013, 16:05 #10
Цитата Сообщение от Olivеr Посмотреть сообщение
C++
1
pos = str.find(match_seq, ++pos)
насколько я знаю тут undefined behavior поэтому и разные копиляторы реагируют по разнумо
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 16:07 #11
Да, все правильно, не заметил. GCC инициализировала нулем. С
C++
1
size_t pos = -1
и строкой "abcHello world! abc...abc...abc...ab" работает?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7423 / 4538 / 673
Регистрация: 29.11.2010
Сообщений: 12,319
09.06.2013, 16:52 #12
Olivеr, мб все-таки int pos = -1?
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 17:01 #13
MrGluck, в int может не поместится. size_t pos = -1, после ++pos получаем ноль. или же long long pos = -1
0
Dragokas
Эксперт WindowsАвтор FAQ
15998 / 6815 / 821
Регистрация: 25.12.2011
Сообщений: 10,555
Записей в блоге: 16
09.06.2013, 17:30 #14
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
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
09.06.2013, 17:35 #15
Цитата Сообщение от 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
09.06.2013, 17:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2013, 17:35
Привет! Вот еще темы с ответами:

Найти все вхождения строки P в текст T, используя наивный алгоритм поиска - C++
Только начал изучать язык С++, не могу никак реализовать: даны строки P и T. Найти все вхождения строки P в текст T, используя наивный...

Необходимо найти самое длинное слово и удалить все его вхождения - C++
самое длинное слово я нахожу, но вот как его удалить? #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;cstring&gt; using...

Найти все возможные подмножества из данного множества - C++
Необходимо написать программу, выводящую все возможные подмножества из данного множества. Выглядить должно примерно так: Массив на...

Найти все действительные решения данного биквадратного уравнения - C++
Найти все действительные решения данного биквадратного уравнения. Именуйте темы осмысленно! Название темы должно максимально полно...


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

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

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