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

@Solnechnayanny · Регистрация: 20.06.2010

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

Добавлено через 4 часа 58 минут
хотя бы какие функции использовать для реализации???Подскажите пожалуйста

@Mr.X · 24.06.2010, 02:59

Мне понятно, что условия задачи вам самой пока непонятны, и вам надо уточнить их с преподавателем.
А где пример, который дал преподаватель?

@Solnechnayanny · 24.06.2010, 03:00 **[ТС]**

строка acacbcbc,шаблон ac*bc,ответ я написала.И метод решения,который я привела является правильным.Просто я предполагаю,что существуют разные способы решения этой задачи.

@Mr.X · 24.06.2010, 03:10

Т.е. он предлагает искать с каждой позиции строки все возможные подстроки. Можно и так сделать, только тогда если, скажем, у вас вначале строки длиной 100000 стоит буква z, и задан шаблон «z*», то первое соответствие будет вся строка, второе - строка без последнего символа, и так сто тысяч раз.

@Solnechnayanny · 24.06.2010, 03:12 **[ТС]**

видимо так..также он упоминал алгоритм shift-or,правда я в нём так и не смогла разобраться=(

@Mr.X · 24.06.2010, 12:24

Итак, возможны три способа поиска соответствующих шаблону подстрок с каждой позиции строки:
1. Искать минимально возможную подстроку (ленивый алгоритм);
2. Искать максимально возможную подстроку (жадный алгоритм);
3. Искать все возможные подстроки.

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

Добавлено через 2 минуты
Программа, отыскивающая максимально возможную подстроку (жадный алгоритм):

C++

//Задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать 
//знак "*", который в свою очередь равен либо пробелу,либо произвольным буквам 
//лат. алфавита. Подсчитать все возможные вхождения шаблона в строку. 
//Шаблон можно вводить и с консоли.
 
//==================================================================================
//  Программа ведет поиск соответствия шаблону слева направо с каждой позиции строки.
//  Для подстановки текста вместо звездочки используется жадный алгоритм.
//==================================================================================
#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++

//Задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать 
//знак "*", который в свою очередь равен либо пробелу,либо произвольным буквам 
//лат. алфавита. Подсчитать все возможные вхождения шаблона в строку. 
//Шаблон можно вводить и с консоли.
 
//==================================================================================
//  Программа ведет поиск соответствия шаблону по строке слева направо, 
//  и с каждой позиции строки отыскивает все возможные подстроки, 
//  соответствующие шаблону.
//==================================================================================
#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;
}

@Solnechnayanny · 24.06.2010, 12:27 **[ТС]**

ещё раз большое спасибо))))

@Solnechnayanny 1 / 1 / 0 Регистрация: 20.06.2010 Сообщений: 43
		#1
	Поиск всех вхождений шаблона в строку - C++ 21.06.2010, 00:31. Просмотров 2333. Ответов 20 Метки нет (Все метки) Здравствуйте,хотела к вам обратиться за помощью..в файле t.txt есть строка из символов букв латинского алфавита,длиной до 100000 знаков. Так же в текстовом файле s.txt задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать знак "",который в свою очередь равен либо пробелу,либо произвольным буквам лат.алфавита.Длина шаблона до 20 символов.Подсчитать все возможные вхождения шаблона в строку.Ответ записать в файл. Как читать файл,разбивать на символы я примерно знаю,но вот как сделать так,чтобы звёздочка заменяла любую комбинацию символов нет..Очень надеюсь на вашу скорую помощь)) P.S.:шаблон можно вводить и с консоли,чтобы не усложнять задачу с считыванием символов)) Добавлено через 4 часа 58 минут хотя бы какие функции использовать для реализации???Подскажите пожалуйста

@Mr.X 3049 / 1694 / 265 Регистрация: 03.05.2010 Сообщений: 3,867
	24.06.2010, 02:59	#16
	Мне понятно, что условия задачи вам самой пока непонятны, и вам надо уточнить их с преподавателем. А где пример, который дал преподаватель?

@Solnechnayanny 1 / 1 / 0 Регистрация: 20.06.2010 Сообщений: 43
	24.06.2010, 03:00 [ТС]	#17
	строка acacbcbc,шаблон ac*bc,ответ я написала.И метод решения,который я привела является правильным.Просто я предполагаю,что существуют разные способы решения этой задачи.

@Mr.X 3049 / 1694 / 265 Регистрация: 03.05.2010 Сообщений: 3,867
	24.06.2010, 03:10	#18
	Т.е. он предлагает искать с каждой позиции строки все возможные подстроки. Можно и так сделать, только тогда если, скажем, у вас вначале строки длиной 100000 стоит буква z, и задан шаблон «z*», то первое соответствие будет вся строка, второе - строка без последнего символа, и так сто тысяч раз.

@Solnechnayanny 1 / 1 / 0 Регистрация: 20.06.2010 Сообщений: 43
	24.06.2010, 03:12 [ТС]	#19
	видимо так..также он упоминал алгоритм shift-or,правда я в нём так и не смогла разобраться=(

@Solnechnayanny 1 / 1 / 0 Регистрация: 20.06.2010 Сообщений: 43
	24.06.2010, 12:27 [ТС]	#21
	ещё раз большое спасибо))))

Yandex Объявления	24.06.2010, 12:27

Опции темы

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

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