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

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

Войти
Регистрация
Восстановить пароль
 
 
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
#1

Найти все вхождения строки P в текст T, используя наивный алгоритм поиска - C++

07.09.2014, 21:33. Просмотров 1398. Ответов 16
Метки нет (Все метки)

Только начал изучать язык С++, не могу никак реализовать: даны строки P и T. Найти все вхождения строки P в текст T, используя наивный алгоритм поиска. Помогите пожалуйста.

Добавлено через 27 минут
очень нужно на завтра..
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2014, 21:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти все вхождения строки P в текст T, используя наивный алгоритм поиска (C++):

Удвоить все найденные вхождения строки в текст - C++
c++ visual Задание: дан текст и строка. удвойте все найденные вхождения строки. насколько я понимаю, если ввести текст "мама мыла раму"...

Найти все вхождения строки s в t - C++
Требуется написать программу, которая выводить на экран идексы всех вхождений строки s в строку t: abababababa aba 0 2 4 6 8 ...

Найти все вхождения строки Т в строке S - C++
Найти все вхождения строки Т в строке S Помогите пожалуйста! И если можно на языке Си!!!

Ввести строку текста и строку поиска, найти местоположение первого вхождения строки поиска в строку текста - C++
Здравствуйте, не могли бы вы помочь новичку в программировании))) Нужно написать програмку, которая считывает с клавиатуры строку текста...

Функция поиска первого вхождения шаблона в текст - C++
. В качестве первого параметра функция принимает текст (C-style строка), в которой нужно искать шаблон. В качестве второго параметра...

Найти наименьшее из четырех чисел используя алгоритм поиска наибольшего из двух чисел - C++
Найти наименьшее из четырех чисел используя алгоритм поиска наибольшего из двух чисел.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16697 / 6623 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 1
07.09.2014, 21:41 #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
#include <iostream>
#include <vector>
 
std::vector<int> findMatches(std::string p, std::string t)
{
    size_t m = p.size() - 1;
    size_t n = t.size();
    std::vector<int> result;
    
    for(size_t i = 0, j = 0; i < n; ++i)
    {
        while(i < n && j != m && t[i] == p[j])
        {
            ++i;
            ++j;
        }
 
        if(j == m)
        {
            result.push_back(i-m);
            j = 0;
        }
    }
    return result;
}
 
int main(int argc, char *argv[])
{
    std::string p = "abc";
    std::string t = "abcaaaabcddabcdd";
    
    std::vector<int> result = findMatches(p, t);
 
    std::cout << std::endl;
    for(std::vector<int>::const_iterator it = result.begin(); it != result.end(); ++it)
        std::cout << *it << std::endl;
}
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
07.09.2014, 22:01 #3
Цитата Сообщение от KOPOJI Посмотреть сообщение
t[i] == p[j] && i < n && j != m
Выход за пределы.
0
KOPOJI
07.09.2014, 22:04
  #4

Не по теме:

Toshkarik, я еще за 10 минут до вашего ответа поменял местами условия..

0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
07.09.2014, 22:05 #5
Написал сообщение и забыл отправить.
0
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
08.09.2014, 18:57  [ТС] #6
Спасибо. А как сделать, чтобы текст вводился с клавиатуры ?
Это в программе:
C++
1
2
 std::string p = "abc";
    std::string t = "abcaaaabcddabcdd";
Пробовал через getline, но тогда не выводит ничего(
0
Kerry_Jr
Модератор
Эксперт PHP
2192 / 1988 / 696
Регистрация: 14.05.2014
Сообщений: 5,825
Записей в блоге: 1
Завершенные тесты: 5
08.09.2014, 19:10 #7
Цитата Сообщение от taeas1995 Посмотреть сообщение
Пробовал через getline, но тогда не выводит ничего(
Код выкладывайте. У меня все получилось, если это
C++
1
2
std::string p = "abc";
std::string t = "abcaaaabcddabcdd";
заменить на это
C++
1
2
3
4
5
std::string p, t;
std::cout << "Enter the pattern string: ";
getline (std::cin, p);
std::cout << "Enter the string: ";
getline (std::cin, t);
1
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
15.09.2014, 11:16  [ТС] #8
Когда я ввожу "aaaaa" и подстроку "аа", то не правильно считает количество подстрок в строке. Вот скрин:
0
Миниатюры
Найти все вхождения строки P в текст T, используя наивный алгоритм поиска  
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
15.09.2014, 11:47  [ТС] #9
помогите исправить пожалуйста
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
15.09.2014, 11:52 #10
Ну почему же неправильно. Все верно. 4 раза встречается "аа" в "ааааа".
Код
aaaaa
aa
 aa
  aa
   aa
0
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
15.09.2014, 11:55  [ТС] #11
Но в программе пишет (0 - 2 - 4), то есть в трёх случаях. (нужно 0 - 1 - 2 - 3).
0
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16697 / 6623 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 1
15.09.2014, 11:59 #12
Замените функцию на такую
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::vector<int> findMatches(std::string p, std::string t)
{
    size_t m = p.size() - 1;
    size_t n = t.size();
    std::vector<int> result;
    
    for(size_t i = 0, j = 0; i < n; ++i)
    {
        if(t[i] == p[j])
        {
            while(++i < n && ++j != m && t[i] == p[j])
                ;
            if(j == m)
            {
                result.push_back(i-m);
                j = 0;
            }
        }
    }
    return result;
}
Добавлено через 1 минуту
taeas1995, а разве в "ааааа" должно быть четыре вхождения "аа", а не два?

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::vector<int> findMatches(std::string p, std::string t)
{
    size_t m = p.size() - 1;
    size_t n = t.size();
    std::vector<int> result;
    
    for(size_t i = 0, j = 0; i < n; ++i)
    {
        if(t[i] == p[j])
        {
            while(++i < n && ++j != m && t[i] == p[j])
                ;
            if(j == m)
            {
                result.push_back(i -= m);
                j = 0;
            }
        }
    }
    return result;
}
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
15.09.2014, 12:01 #13
Ну с этим всегда по разному, обычно это обговаривается в условии задания.
0
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16697 / 6623 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 1
15.09.2014, 12:02 #14
ну я уже привел оба варианта...
0
worldown
43 / 43 / 20
Регистрация: 22.06.2009
Сообщений: 156
15.09.2014, 12:55 #15
Еще вот такой вариант, без векторов..
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
#include <iostream>
using namespace std;
 
void find(char *text);
 
int main() {
    //текст, в котором производиться поиск
    char *text = "abcaabcaaab";
    find(text);
    system("pause");
    return 0;
}
 
void find(char *text) {
    char *sr = new char;
    int counter = 0;
 
    cout<<"Enter what you need to find: ";
    cin>>sr;
    for(int j = 0, i = 0; text[j]; j++){
        if(sr[i] == text[j]) {
            i++;
            if(sr[i] == '\0') {
            i = 0;
            counter++;
            }
        }
        else {
            j-=i;
            i=0;
        }
    }
    cout<<"The word \""<<sr<<"\" in the text \""<<text<<"\" found "<<counter<<" time(s)"<<endl;
    return;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2014, 12:55
Привет! Вот еще темы с ответами:

Наивный алгоритм для задачи о рюкзаке - C++
Всем привет помогите написать программу о рюкзаке c с помощью наивного алгоритма. Я начал, а дальше не совсем понимаю, что сделать нужно....

Функция поиска вхождения строки в заданную строку в С - C++
получил в универе такое задание Функция - Findwords(s,s1). Назначение - поиск вхождения в строку s заданной фразы (последовательности...

Процедура поиска вхождения одной строки в другой - C++
Написать программу, которая вводит с клавиатуры три строки длиной не более 200 символов, заменяет в первой строке все вхождения второй...

Используя алгоритм бинарного поиска определите - C++
Используя алгоритм бинарного поиска определите , содержит ли ранее упорядоченный массив заданное действительное число. Если содержит ,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.09.2014, 12:55
Ответ Создать тему
Опции темы

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