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

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

Восстановить пароль Регистрация
 
Novicheki
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 22
08.06.2013, 20:04     Найти в тексте все вхождения данного образца #1
Буду рад любой помощи
вообще непонятна сама организация поиска, помогите пожалуйста
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
 Аватар для dr.curse
386 / 342 / 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
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;
}
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
09.06.2013, 00:41     Найти в тексте все вхождения данного образца #4
Цитата Сообщение от Novicheki Посмотреть сообщение
все вхождения данного образца
Aho–Corasick string matching algorithm
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
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;
}
Dragokas
Автор FAQ
 Аватар для Dragokas
14511 / 6338 / 783
Регистрация: 25.12.2011
Сообщений: 9,866
Записей в блоге: 14
09.06.2013, 03:06     Найти в тексте все вхождения данного образца #6
Olivеr, инициализировать так?
C++
1
size_t pos = -1;
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
09.06.2013, 15:14     Найти в тексте все вхождения данного образца #7
Dragokas, в данном случае инициализировать не обязательно, ведь в цикле есть присвоение результата функции string::find() которая в любом случае вернет или конкретную позицию или string::npos (то, что вы написали). А если все таки инициализировать, то лучше так:
C++
1
size_t pos = static_cast<size_t>(-1);
Dragokas
Автор FAQ
 Аватар для Dragokas
14511 / 6338 / 783
Регистрация: 25.12.2011
Сообщений: 9,866
Записей в блоге: 14
09.06.2013, 16:01     Найти в тексте все вхождения данного образца #8
Olivеr, присвоение есть, но сначала происходит инкремент ++pos, а начальное значение не присвоено.
Мой VS 2012 на это ругается.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,402
09.06.2013, 16:04     Найти в тексте все вхождения данного образца #9
Olivеr, ищет то от ++pos, которое на момент поиска еще не очевидно, т.е. pos ни к чем не приравнивалось и может быть чем угодно
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.06.2013, 16:05     Найти в тексте все вхождения данного образца #10
Цитата Сообщение от Olivеr Посмотреть сообщение
C++
1
pos = str.find(match_seq, ++pos)
насколько я знаю тут undefined behavior поэтому и разные копиляторы реагируют по разнумо
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
09.06.2013, 16:07     Найти в тексте все вхождения данного образца #11
Да, все правильно, не заметил. GCC инициализировала нулем. С
C++
1
size_t pos = -1
и строкой "abcHello world! abc...abc...abc...ab" работает?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,402
09.06.2013, 16:52     Найти в тексте все вхождения данного образца #12
Olivеr, мб все-таки int pos = -1?
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
09.06.2013, 17:01     Найти в тексте все вхождения данного образца #13
MrGluck, в int может не поместится. size_t pos = -1, после ++pos получаем ноль. или же long long pos = -1
Dragokas
Автор FAQ
 Аватар для Dragokas
14511 / 6338 / 783
Регистрация: 25.12.2011
Сообщений: 9,866
Записей в блоге: 14
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 окажется по другую сторону стека.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
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, если результат предыдущей арифметической операции над числами со знаком выходит за допустимые для них пределы. Например, если при сложении двух положительных чисел получается число со старшим битом, равным единице (то есть отрицательное) и наоборот.
Т.е. только для знаковых
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,402
09.06.2013, 18:19     Найти в тексте все вхождения данного образца #16
Цитата Сообщение от Olivеr Посмотреть сообщение
в int может не поместится
всего лишь в 2 раза меньше диапазон, чем у size_t.
Это ничто по сравнению с записью в unsigned отрицательных чисел.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
09.06.2013, 18:27     Найти в тексте все вхождения данного образца #17
Цитата Сообщение от 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);
...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2013, 18:35     Найти в тексте все вхождения данного образца
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,402
09.06.2013, 18:35     Найти в тексте все вхождения данного образца #18
Полез в стандарт:
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 ...
Yandex
Объявления
09.06.2013, 18:35     Найти в тексте все вхождения данного образца
Ответ Создать тему
Опции темы

Текущее время: 12:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru