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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Создать массив http://www.cyberforum.ru/cpp-beginners/thread147754.html
1. Создать массив, состоящий из указанного в таблице количества элементов, указанного типа. Заполнить массив числами, согласно заданному в таблице правилу. Вывести сначала все элементы массива в прямом порядке (т.е. по возрастанию индексов), а затем элементы, соответствующие указанному в таблице критерию, в обратном порядке. int, 50 Арифметическая прогрессия с известным первым членом...
C++ Длинная арифметика Здравствуйте! Есть задание: Составить программу для вычисления числа: (2^64) - 1. В результате сохранить все цифры. 2^64 - это 2 в 64-ой степени. Если честно - то таких задач никогда и не решал. И на занятиях таких работ не было. За то на практике задачу такую дали. Есть код, который "вроде как" с этой задачей справляется: http://www.cyberforum.ru/cpp-beginners/thread147747.html
C++ Составить программу для проверки, есть ли в массиве одинаковые элементы. Проверить на наличие одинаковых элементов линейные таблицы А [10] и В [12]. И
Составить программу для проверки, есть ли в массиве одинаковые элементы. Проверить на наличие одинаковых элементов линейные таблицы А и В . Инициализацию, вывод элементов массива, их обработку организовать в отдельных функциях. Добавлено через 1 час 14 минут мальчики помогите
Составить программу, которая вычисляет количество элементов одномерного массива Х, состоящего из 15 вещественных чисел, которые равняются по значению C++
Составить программу, которая вычисляет количество элементов одномерного массива Х, состоящего из 15 вещественных чисел, которые равняются по значению максимальному элементу.
C++ блок схема http://www.cyberforum.ru/cpp-beginners/thread147718.html
нарисуйте плиз блок схему для етой части кода: #include <iostream.h> #include <stdio.h> #include <conio.h> #include <string.h> #include <windows.h> int i; void crypt(); void decrypt(); void create();
C++ Прямоугольная матрица В прямоугольной матрице часть элементов имеют нулевое значение. Заменить каждый нулевой элемент суммой смежных ему элементов (по горизонтали, вертикали и диагоналям). Формирование новой матрицы выполнять в буферном массиве. подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
24.06.2010, 12:24     поиск всех вхождений шаблона в строку
Итак, возможны три способа поиска соответствующих шаблону подстрок с каждой позиции строки:
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;
}
 
Текущее время: 05:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru