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

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

Восстановить пароль Регистрация
 
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
07.09.2014, 21:33     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #1
Только начал изучать язык С++, не могу никак реализовать: даны строки P и T. Найти все вхождения строки P в текст T, используя наивный алгоритм поиска. Помогите пожалуйста.

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

C++ Функция поиска вхождения строки в заданную строку в С
Найти все вхождения строки s в t C++
Найти все вхождения строки Т в строке S C++
Удвоить все найденные вхождения строки в текст C++
Используя алгоритм бинарного поиска определите C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KOPOJI
Модератор
 Аватар для KOPOJI
16243 / 6454 / 390
Регистрация: 12.06.2012
Сообщений: 19,362
07.09.2014, 21:41     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #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;
}
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
07.09.2014, 22:01     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #3
Цитата Сообщение от KOPOJI Посмотреть сообщение
t[i] == p[j] && i < n && j != m
Выход за пределы.
KOPOJI
07.09.2014, 22:04
  #4

Не по теме:

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

Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
07.09.2014, 22:05     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #5
Написал сообщение и забыл отправить.
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
08.09.2014, 18:57  [ТС]     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #6
Спасибо. А как сделать, чтобы текст вводился с клавиатуры ?
Это в программе:
C++
1
2
 std::string p = "abc";
    std::string t = "abcaaaabcddabcdd";
Пробовал через getline, но тогда не выводит ничего(
Kerry_Jr
Модератор
 Аватар для Kerry_Jr
1868 / 1664 / 580
Регистрация: 14.05.2014
Сообщений: 4,779
Записей в блоге: 1
Завершенные тесты: 5
08.09.2014, 19:10     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #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);
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
15.09.2014, 11:16  [ТС]     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #8
Когда я ввожу "aaaaa" и подстроку "аа", то не правильно считает количество подстрок в строке. Вот скрин:
Миниатюры
Найти все вхождения строки P в текст T, используя наивный алгоритм поиска  
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
15.09.2014, 11:47  [ТС]     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #9
помогите исправить пожалуйста
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
15.09.2014, 11:52     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #10
Ну почему же неправильно. Все верно. 4 раза встречается "аа" в "ааааа".
Код
aaaaa
aa
 aa
  aa
   aa
taeas1995
6 / 2 / 0
Регистрация: 19.01.2012
Сообщений: 157
15.09.2014, 11:55  [ТС]     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #11
Но в программе пишет (0 - 2 - 4), то есть в трёх случаях. (нужно 0 - 1 - 2 - 3).
KOPOJI
Модератор
 Аватар для KOPOJI
16243 / 6454 / 390
Регистрация: 12.06.2012
Сообщений: 19,362
15.09.2014, 11:59     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #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;
}
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
15.09.2014, 12:01     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #13
Ну с этим всегда по разному, обычно это обговаривается в условии задания.
KOPOJI
Модератор
 Аватар для KOPOJI
16243 / 6454 / 390
Регистрация: 12.06.2012
Сообщений: 19,362
15.09.2014, 12:02     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #14
ну я уже привел оба варианта...
worldown
33 / 33 / 15
Регистрация: 22.06.2009
Сообщений: 124
15.09.2014, 12:55     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #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;
}
KOPOJI
Модератор
 Аватар для KOPOJI
16243 / 6454 / 390
Регистрация: 12.06.2012
Сообщений: 19,362
15.09.2014, 13:01     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #16
worldown, "найти вхождения" != "подсчитать количество вхождений"..

Добавлено через 1 минуту
собственно, вектор и использовался лишь для хранения найденных вхождений, не более того.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2014, 13:26     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска
Еще ссылки по теме:

Алгоритм поиска строки в тексте C++
C++ Стек. Выведите все вхождения символов указанного набора в текст в обратном порядке
Ввести строку текста и строку поиска, найти местоположение первого вхождения строки поиска в строку текста C++

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

Или воспользуйтесь поиском по форуму:
worldown
33 / 33 / 15
Регистрация: 22.06.2009
Сообщений: 124
15.09.2014, 13:26     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска #17
KOPOJI

Не по теме:

каюсь. Не въехал в суть сего вопроса

Yandex
Объявления
15.09.2014, 13:26     Найти все вхождения строки P в текст T, используя наивный алгоритм поиска
Ответ Создать тему
Опции темы

Текущее время: 13:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru