Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
|
|
#1 | |
Поиск всех вхождений шаблона в строку - C++21.06.2010, 00:31. Просмотров 2453. Ответов 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++):
20
Количество вхождений всех символов в строку - C++ Подсчитать количество вхождений слова «мама» в строку и вывести номера первых позиций этих вхождений - C++ Написать программу, которая выводит позиции всех вхождений гена в геном (поиск гена) - C++ Создать функцию, которая на вход получает строку символов, сообщает количество вхождений каждой цифры в строку... - C++ Подсчет вхождений подстроки в строку - C++ Подсчет вхождений символа в строку - C++ |
Mr.X
![]() 3056 / 1701 / 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
![]() 3056 / 1701 / 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
![]() 3056 / 1701 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
|
|||||||||||
24.06.2010, 12:24 | #20 | ||||||||||
Итак, возможны три способа поиска соответствующих шаблону подстрок с каждой позиции строки:
1. Искать минимально возможную подстроку (ленивый алгоритм); 2. Искать максимально возможную подстроку (жадный алгоритм); 3. Искать все возможные подстроки. Мое решение первым способом приведено выше. Добавлено через 2 минуты Программа, отыскивающая максимально возможную подстроку (жадный алгоритм):
Программа, отыскивающая все возможные подстроки:
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 |
Привет! Вот еще темы с ответами:
21
Функция замены всех вхождений подстроки - C++ Найти количество вхождений строки S0 в строку S - C++ Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |