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

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

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

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

21.06.2010, 00:31. Просмотров 2410. Ответов 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
Egeni
10 / 10 / 1
Регистрация: 17.06.2010
Сообщений: 107
Записей в блоге: 1
21.06.2010, 01:30 #2
а что есть уже из наработанного?


вот функция поиска [C++] Работа с файлами
1
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
21.06.2010, 02:09  [ТС] #3
есть программа поиска шаблона в тексте,но в maple..и она правда тоже не до конца доработана..вся загвоздка в "*"...я просто не сильна в си/си++..я на первом курсе изучала только паскаль..а потом перевелась..и с изучением новых языков есть сложности..
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
22.06.2010, 14:15  [ТС] #4
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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
 
int main(int argc, char *argv[])
{
 
int filedes_t; 
int filedes_p; 
ssize_t nread;
ssize_t rread;
char text[1050000]; // ïîñëåäîâГ*òëüГ*îñòü
char pattern[30]; // ïîäïîñëåäîâГ*òåëüГ*îñòü
char *pref, *suf;
 
if (argc != 3) {
printf("input 2 argument - ./filename text pattern\n");
return 1;
}
 
if ((filedes_p = open(argv[2], O_RDONLY)) == -1) {
printf("cant open pattern file\n");
return 1;
}
 
if ((filedes_t = open(argv[1], O_RDONLY)) == -1) {
printf("cant open text file\n");
return 1;
}
 
if ((rread = read(filedes_p, pattern, 30)) == -1) {
printf("ERROR read pattern\n");
return 1;
}
 
if ((nread = read(filedes_t, text, 1000000)) == -1) {
printf("ERROR read text\n");
return 1;
}
void main(){
pref = strtok_r(pattern, "*", &suf);
printf ("%s\n", pref);
printf ("%s\n", suf);
 
long int[] n, m;
int i,j,p,l;
for (i=0;i<strlen(text);i++)
{
n[i]=strstr_cnt(text,pref);
printf("%d \n",n[i]);
}
for (j=0;j<strlen(text);j++)
{
m[j]=strstr_cnt(text,suf);
printf("%d \n",m[j]);
}
p=sizeof(n[i]);
l=sizeof(m[j]);
for(i=0; i<p; i++)
for(j=0; j<l; j++)
if(n[i]+strlen(pref)< m[j])
printf("Г*Г*øëè âõîæäåГ*ГЁГҐ Г± %d ГЇГ® %d\n", n[i], m[j]+strlen(suf)); 
}
}
В чём тут ошибка?почему метод strtok_r при компиляции выдаёт ошибку,а от туда и дальше прога не ладится(((((((((((Мои наработки
0
Aaxenon
Light Knight
106 / 29 / 3
Регистрация: 03.06.2010
Сообщений: 361
22.06.2010, 14:56 #5
а какая выдается ошибка
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
22.06.2010, 22:19  [ТС] #6
выдает ошибку :[Warning] assignment makes pointer from integer without a cast
я ещё немного код передела..и снова вылезла уйма ошибок((

Добавлено через 1 минуту
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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
 
int main(int argc, char *argv[])
{
 
int filedes_t; 
int filedes_p; 
ssize_t nread;
ssize_t rread;
char text[1050000]; // ïîñëåäîâГ*òëüГ*îñòü
char pattern[30]; // ïîäïîñëåäîâГ*òåëüГ*îñòü
char *pref, *suf;
 
if (argc != 3) {
printf("input 2 argument - ./filename text pattern\n");
return 1;
}
 
if ((filedes_p = open(argv[2], O_RDONLY)) == -1) {
printf("cant open pattern file\n");
return 1;
}
 
if ((filedes_t = open(argv[1], O_RDONLY)) == -1) {
printf("cant open text file\n");
return 1;
}
 
if ((rread = read(filedes_p, pattern, 30)) == -1) {
printf("ERROR read pattern\n");
return 1;
}
 
if ((nread = read(filedes_t, text, 1000000)) == -1) {
printf("ERROR read text\n");
return 1;
}
pref = strtok_r(pattern, "*", &suf);
printf ("%s\n", pref);
printf ("%s\n", suf);
 
int strstr_cnt(const char *Src,const char *Sub)
{
  int count = 0;
  long int len = strlen(Src);
  for (int i=0; i<len; i++)
  {
    if(Sub[0]==Src[i])
    {
    bool is = true;
    for(int j=0; j<strlen(Sub); j++)
    if(i+j<len)
    {
                 if(Sub[j]!=Src[i+j]) is=false;
    }
    else is=false;
    if(is) count++;
     }
  }
  return count;
}
long int[] n, m;
int i,j,p,j;
for (i=0;i<strlen(text);i++)
{
 n[i]=strstr_cnt(text,pref);
    printf("%d \n",n[i]);
}
    for (j=0;j<strlen(text);j++)
    {
     m[j]=strstr_cnt(text,suf);
     printf("%d \n",m[j]);
        }
p=sizeof(n[i]);
l=sizeof(m[j]);
      for(i=0; i<p; i++)
for(j=0; j<l; j++)
if(n[i]+strlen(pref)< m[j])
printf("Г*Г*øëè âõîæäåГ*ГЁГҐ Г± %d ГЇГ® %d\n", n[i], m[j]+strlen(suf));  
}
}
0
Aaxenon
Light Knight
106 / 29 / 3
Регистрация: 03.06.2010
Сообщений: 361
22.06.2010, 22:20 #7
а нужен с или с++?
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
22.06.2010, 22:22  [ТС] #8
С..ошиблась с выбором кода в выделении)..ну если другую прогу делать,то без разницы..)
0
accept
4828 / 3249 / 165
Регистрация: 10.12.2008
Сообщений: 10,569
23.06.2010, 08:42 #9
C
1
int strstr_cnt(const char *Src,const char *Sub)
эта функция не может быть в функции main(), её всю нужно вынести наружу
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.06.2010, 16:35 #10
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
//Задаётся шаблон, в котором кроме букв латинского алфавита может присутствовать 
//знак "*", который в свою очередь равен либо пробелу,либо произвольным буквам 
//лат. алфавита. Подсчитать все возможные вхождения шаблона в строку. 
//Шаблон можно вводить и с консоли.
 
//==================================================================================
//  Программа ведет поиск соответствия шаблону слева направо с каждой позиции строки.
//  Для подстановки текста вместо звездочки используется ленивый алгоритм.
//==================================================================================
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
 
typedef std::string       T_str;
typedef T_str::size_type  T_pos;
 
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) pattern += METASYMBOL;
 
    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_find_pos  = pref_pos + metasymbol_pos;
        T_pos  suf_pos       = str.find(suf, suf_find_pos);
 
        if(suf_pos == T_str::npos) 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;
}
1
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
23.06.2010, 22:08  [ТС] #11
спасибо огромное..)))правда есть одна беда,видимо у меня с компиляторм..не удаётся посмотреть результат(((
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.06.2010, 22:29 #12
Цитата Сообщение от Solnechnayanny Посмотреть сообщение
спасибо огромное..)))правда есть одна беда,видимо у меня с компиляторм..не удаётся посмотреть результат(((
В смысле?
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
24.06.2010, 01:39  [ТС] #13
окно сразу закрывается после ввода шаблона..у меня программа Bloodshed dev-c++

Добавлено через 44 минуты
ответ я увидела,но задача считает не все возможные вхождения...к примеру для acacbcbc,шаблон ac*bc входит в строку 4 раза:acacbc;acacbcbc,acbc,acbcbc.А прога находит лишь acacbc;acbc=(((
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.06.2010, 02:31 #14
Цитата Сообщение от Solnechnayanny Посмотреть сообщение
окно сразу закрывается после ввода шаблона..у меня программа Bloodshed dev-c++

Добавлено через 44 минуты
ответ я увидела,но задача считает не все возможные вхождения...к примеру для acacbcbc,шаблон ac*bc входит в строку 4 раза:acacbc;acacbcbc,acbc,acbcbc.А прога находит лишь acacbc;acbc=(((
Так вы наверно это еще не читали:
http://www.cyberforum.ru/cpp-beginners/thread10807.html
Мне легче, у меня в Visual Studio ничего никуда не исчезает.

А насчет подстрок - вы уже определитесь что вам нужно. В примере, который вы приводили в параллельной теме, с каждой позиции строки вычислялась подстрока по ленивому алгоритму, т.е. наименьшая из возможных. А здесь вы предлагаете с каждой позиции вычислять одновременно и по ленивому и по жадному алгоритму. Те примеры вы откуда взяли? Если вам преподаватель дал, то моя программа по ним сделана и их выполняет. Если нужно что-то другое, то нужно четче формулировать.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
24.06.2010, 02:39  [ТС] #15
извините,если не смогла до вас донести суть задания..не всегда получается его чётко сформулировать ...те примеры взяты с головы,чтобы более или менее объяснить,что мне нужно..преподаватель дал 2 пример)каким алгоритмом решать я не знаю,но предполагаю,что жадным..я пыталась разбить шаблон на префикс и суффикс,а затем отдельно найти вхождения того и другого..а затем выбрать те пары,где ac находится перед bc..надеюсь теперь стало понятнее
0
24.06.2010, 02:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.06.2010, 02:39
Привет! Вот еще темы с ответами:

Количество вхождений строки 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.


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

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

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