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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
#1

Поиск всех вхождений шаблона в строку - C++

21.06.2010, 00:31. Просмотров 2408. Ответов 20
Метки нет (Все метки)

Здравствуйте,хотела к вам обратиться за помощью..в файле t.txt есть строка из символов букв латинского алфавита,длиной до 100000 знаков. Так же в текстовом файле s.txt задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать знак "*",который в свою очередь равен либо пробелу,либо произвольным буквам лат.алфавита.Длина шаблона до 20 символов.Подсчитать все возможные вхождения шаблона в строку.Ответ записать в файл.
Как читать файл,разбивать на символы я примерно знаю,но вот как сделать так,чтобы звёздочка заменяла любую комбинацию символов нет..Очень надеюсь на вашу скорую помощь*))
P.S.:шаблон можно вводить и с консоли,чтобы не усложнять задачу с считыванием символов))

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

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

Подсчитать количество вхождений слова «мама» в строку и вывести номера первых позиций этих вхождений - C++
Помогите исправить ошибку. Как вывести номера первых позиций вхождений слова мама? Подсчитать количество вхождений слова «мама» в строку...

Написать программу, которая выводит позиции всех вхождений гена в геном (поиск гена) - C++
Задан геном некоторого организма (последовательность букв A T G C (аденин, тимин, гуанин, цитозин). Также задан некоторый ген (тоже...

Создать функцию, которая на вход получает строку символов, сообщает количество вхождений каждой цифры в строку... - C++
Создать функцию, которая на вход получает строку символов, сообщает количество вхождений каждой цифры в строку и в случае, если цифр 5, 6,...

Подсчет вхождений подстроки в строку - C++
Здравствуйте, помогите найти ошибку, в файле есть строки например S1gfgd S2vsdfvbf S1ffgv необходимо подсчитать сколько раз...

Подсчет вхождений символа в строку - C++
Для каждого символа латинского алфавита найдите число его вхождений в строку (можно придумать алгоритм, работающий за линейное время от...

20
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.06.2010, 02:59 #16
Мне понятно, что условия задачи вам самой пока непонятны, и вам надо уточнить их с преподавателем.
А где пример, который дал преподаватель?
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
24.06.2010, 03:00  [ТС] #17
строка acacbcbc,шаблон ac*bc,ответ я написала.И метод решения,который я привела является правильным.Просто я предполагаю,что существуют разные способы решения этой задачи.
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.06.2010, 03:10 #18
Т.е. он предлагает искать с каждой позиции строки все возможные подстроки. Можно и так сделать, только тогда если, скажем, у вас вначале строки длиной 100000 стоит буква z, и задан шаблон «z*», то первое соответствие будет вся строка, второе - строка без последнего символа, и так сто тысяч раз.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
24.06.2010, 03:12  [ТС] #19
видимо так..также он упоминал алгоритм shift-or,правда я в нём так и не смогла разобраться=(
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.06.2010, 12:24 #20
Итак, возможны три способа поиска соответствующих шаблону подстрок с каждой позиции строки:
1. Искать минимально возможную подстроку (ленивый алгоритм);
2. Искать максимально возможную подстроку (жадный алгоритм);
3. Искать все возможные подстроки.

Мое решение первым способом приведено выше.

Добавлено через 2 минуты
Программа, отыскивающая максимально возможную подстроку (жадный алгоритм):
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//Задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать 
//знак "*", который в свою очередь равен либо пробелу,либо произвольным буквам 
//лат. алфавита. Подсчитать все возможные вхождения шаблона в строку. 
//Шаблон можно вводить и с консоли.
 
//==================================================================================
//  Программа ведет поиск соответствия шаблону слева направо с каждой позиции строки.
//  Для подстановки текста вместо звездочки используется жадный алгоритм.
//==================================================================================
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
 
typedef std::string       T_str;
typedef T_str::size_type  T_pos;
 
int  get_chislo_vxozhdeniy_podstrok_v_str
    (
        T_str substr,
        T_str str        
    )
{
    int count = 0;
    for(T_str::size_type  substr_find_pos = 0;; ++count)
    {
        T_str::size_type  substr_pos = str.find(substr, substr_find_pos);        
        if(substr_pos == T_str::npos) break;                
        substr_find_pos = substr_pos + 1;
        std::cout << "Позиция в строке "
                  << std::setw(2)
                  << substr_pos
                  << ": " 
                  << substr
                  << std::endl;
    }
    return count;
}
 
int  get_chislo_vxozhdeniy_shablona_v_str
    (
        T_str pattern,
        T_str str        
    )
{
    std::cout << std::endl;
 
    const char  METASYMBOL         = '*';
    int         metasymbols_total  = std::count
                                     (pattern.begin(), pattern.end(), METASYMBOL);
 
    if(metasymbols_total > 1)  return 0;    
    if(metasymbols_total == 0)
    {
        return get_chislo_vxozhdeniy_podstrok_v_str(pattern, str);
    }
 
    T_pos  metasymbol_pos  = pattern.find(METASYMBOL);
    T_str  pref            = pattern.substr(0, metasymbol_pos);
    T_str  suf             = pattern.substr(metasymbol_pos + 1);
    int    count           = 0;
 
    for(T_pos  pref_find_pos = 0;; ++count)    
    {
        T_pos  pref_pos = str.find(pref, pref_find_pos);
        if(pref_pos == T_str::npos) break; 
        T_pos  suf_pos = str.rfind(suf);
        if(suf_pos == T_str::npos
           || suf_pos < pref_pos + metasymbol_pos) break;                
        pref_find_pos = pref_pos + 1;        
        std::cout << "Позиция в строке "
                  << std::setw(2)
                  << pref_pos
                  << ": "                  
                  << str.substr(pref_pos, suf_pos + suf.length() - pref_pos)
                  << std::endl;
    }
    return count;
}
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите строку:" 
              << std::endl;
    T_str str;
    getline(std::cin, str);
    std::cout << "Введите шаблон:"               
              << std::endl;
    T_str pattern;
    getline(std::cin, pattern);
    
    std::cout << "Число вхождений шаблона в строку равно "
              << get_chislo_vxozhdeniy_shablona_v_str(pattern, str)
              << "."
              << std::endl;   
    return 0;
}
Добавлено через 2 минуты
Программа, отыскивающая все возможные подстроки:
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//Задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать 
//знак "*", который в свою очередь равен либо пробелу,либо произвольным буквам 
//лат. алфавита. Подсчитать все возможные вхождения шаблона в строку. 
//Шаблон можно вводить и с консоли.
 
//==================================================================================
//  Программа ведет поиск соответствия шаблону по строке слева направо, 
//  и с каждой позиции строки отыскивает все возможные подстроки, 
//  соответствующие шаблону.
//==================================================================================
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
 
typedef std::string       T_str;
typedef T_str::size_type  T_pos;
 
int  get_chislo_vxozhdeniy_podstrok_v_str
    (
        T_str substr,
        T_str str        
    )
{
    int count = 0;
    for(T_str::size_type  substr_find_pos = 0;; ++count)
    {
        T_str::size_type  substr_pos = str.find(substr, substr_find_pos);        
        if(substr_pos == T_str::npos) break;                
        substr_find_pos = substr_pos + 1;
        std::cout << "Позиция в строке "
                  << std::setw(2)
                  << substr_pos
                  << ": " 
                  << substr
                  << std::endl;
    }
    return count;
}
 
int  get_chislo_vxozhdeniy_shablona_v_str
    (
        T_str  pattern,
        T_str  str        
    )
{
    std::cout << std::endl;
 
    const char  METASYMBOL         = '*';
    int         metasymbols_total  = std::count
                                     (pattern.begin(), pattern.end(), METASYMBOL);
 
    if(metasymbols_total > 1)  return 0;    
    if(metasymbols_total == 0)
    {
        return get_chislo_vxozhdeniy_podstrok_v_str(pattern, str);
    }
 
    T_pos  metasymbol_pos  = pattern.find(METASYMBOL);
    T_str  pref            = pattern.substr(0, metasymbol_pos);
    T_str  suf             = pattern.substr(metasymbol_pos + 1);
    int    count           = 0;
 
    for(T_pos  pref_find_pos = 0; ; )    
    {
        T_pos  pref_pos = str.find(pref, pref_find_pos);
        if(pref_pos == T_str::npos) break;
 
        for(T_pos  suf_find_pos  = pref_pos + metasymbol_pos; ; ++count)
        {
            T_pos  suf_pos = str.find(suf, suf_find_pos);
            if(suf_pos == T_str::npos)
            {
                pref_find_pos = pref_pos + 1;
                break;
            }                    
            std::cout << "Позиция в строке "
                      << std::setw(2)
                      << pref_pos
                      << ": "                  
                      << str.substr(pref_pos, suf_pos + suf.length() - pref_pos)
                      << std::endl;            
            suf_find_pos = suf_pos + 1;
        }        
    }
    return count;
}
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите строку:" 
              << std::endl;
    T_str str;
    getline(std::cin, str);
    std::cout << "Введите шаблон:"               
              << std::endl;
    T_str pattern;
    getline(std::cin, pattern);
    
    std::cout << "Число вхождений шаблона в строку равно "
              << get_chislo_vxozhdeniy_shablona_v_str(pattern, str)
              << "."
              << std::endl;   
    return 0;
}
1
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
24.06.2010, 12:27  [ТС] #21
ещё раз большое спасибо))))
0
24.06.2010, 12:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.06.2010, 12:27
Привет! Вот еще темы с ответами:

Количество вхождений строки S2 в строку S1 - C++
Строки S1 и S2 вводятся с клавиатуры. Определить является ли строка S2 подстрокой строки S1. Если да, то подсчитать количество вхождений...

Удаление всех вхождений числа в список - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; struct link { int data; link* next; };

Функция замены всех вхождений подстроки - C++
Необходимо написать функцию типа функции PHP str_replace , которая возвращает строку, в которой все вхождения search заменены на replace....

Найти количество вхождений строки S0 в строку S - C++
Введении строки S и S0. Найти количество вхождений строки S0 в строку S.


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

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

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