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

Поиск подстроки - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.63
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 14:49     Поиск подстроки #1
Привет всем. Я пишу программу для поиска подстроки. Если подстрока есть в строке, вывести YES. Иначе - NO.
Вот код(еще не дописанный)
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
int search(char a[], char b[]){
    int i, j, n, m;
    n = strlen(a);
    m = strlen(b);
    int *c = (int*)malloc(m*sizeof(int));
 
    c[0] = 0;
    for(i = 1, j = 0; i < m;i++)
    {
        while(j > 0 && b[j] != b[i])
            j = c[j-1];
        if(b[j] == b[i])
            j++;
        c[i] = j;
 
        for(i = 0,j = 0;i < n;i++){
            while(j > 0 && b[j] != a[i])
                j = c[j-1];
            if(b[j] == a[i]);
            j++;
            if(j == m)
            {
                free(c);
                return i-j+1;
            }
        }
        free(c);
        return -1;
    }
}
 
int main()
{
    char *a[1000000];
    char *b[1000000];
 
    scanf("%s", a);
    scanf("%s", b);
 
    search(a,b)
У меня 2 вопроса. Какие аргументы нужно ввести в вызове функции?
C++
1
search(a,b)
Если я ввожу так, подчеркивает a и b. Если пишу так
C++
1
search(char a[], char b[])
тоже подчеркивает.
И второй вопрос. Как сделать проверку на наличие подстроки в строке? Я так понимаю, что эта функция
C++
1
search(a,b)
принимает значения 1 и -1. Если 1, то YES. Если -1, то NO. Я прав?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Akelle
0 / 0 / 0
Регистрация: 06.06.2014
Сообщений: 5
06.06.2014, 16:18     Поиск подстроки #2
Как вы объявляете a и b, которые передаете функции в первом варианте?

Судя по коду, в случае нахождения подстроки функция должна возвращать индекс начала подстроки в строке.

P.S. 1) У вас не проинициализирована переменная j. 2) В цикле (15-16 строки) не меняется счетчик цикла, т.е. можете бесконечно проверять условие для одного элемента. То же самое в 22-23 строках. 3) вам не нужен цикл из 13-й строчки
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 16:25     Поиск подстроки #3
C++
1
2
3
4
char a[1000000];
char b[1000000];
...
search(a,b);
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 18:17  [ТС]     Поиск подстроки #4
alsav22, Спасибо. Теперь аргументы не подчеркивает. Не подскажете, как теперь сделать проверку на наличие подстроки в строке? Индекс начала подстроки в строке - это i-j+1?

Добавлено через 2 минуты
Я просто взял реализацию алгоритма отсюда http://ru.wikibooks.org/wiki/%D0%9F%...82%D1%82%D0%B0

Добавлено через 37 минут
Вопрос еще в силе. Скажите, как теперь сделать проверку на наличие подстроки в строке? Никак не могу понять.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 18:33     Поиск подстроки #5
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
как теперь сделать проверку на наличие подстроки в строке?
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
char* search(char a[], char b[])
{
    return strstr(a, b);
}
 
int main()
{
    char a[100000];
    char b[100000];
 
    gets(a);
    gets(b);
   
    if (search(a, b))
        printf("YES\n");
    else
        printf("NO\n");
 
    return 0;
}
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 19:02  [ТС]     Поиск подстроки #6
alsav22,
C++
1
2
3
4
char* search(char a[], char b[])
{
    return strstr(a, b);
}
Это дополнение к моей программе? Если да, то выводит ошибку "перегруженная функция". Мне просто нужно реализовать алгоритм КМП в программе. Я попробовал так
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
int search(char a[], char b[]){
    int i, j, n, m;
    n = strlen(a);
    m = strlen(b);
    int *c = (int*)malloc(m*sizeof(int));
 
    c[0] = 0;
    for(i = 1, j = 0; i < m;i++)
    {
        while(j > 0 && b[j] != b[i])
            j = c[j-1];
        if(b[j] == b[i])
            j++;
        c[i] = j;
 
        for(i = 0,j = 0;i < n;i++){
            while(j > 0 && b[j] != a[i])
                j = c[j-1];
            if(b[j] == a[i]);
            j++;
            if(j == m)
            {
                free(c);
                return i-j+1;
            }
        }
        free(c);
        return -1;
    }
}
 
int main()
{
    char a[1000000];
    char b[1000000];
 
    scanf("%s", a);
    scanf("%s", b);
 
    if(search(a,b))
        printf("YES");
    else
        printf("NO");
    getch();
 
    return 0;
}
Пишет "Stack overflow".
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 19:14     Поиск подстроки #7
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Это дополнение к моей программе?
Нет. Это:
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
как теперь сделать проверку на наличие подстроки в строке?
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
06.06.2014, 19:35     Поиск подстроки #8
Сделайте так:

Для начала надо научиться считать префикс-функцию от строки
C++
1
2
3
4
5
6
7
8
9
vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=0; i<n; ++i)
        for (int k=0; k<=i; ++k)
            if (s.substr(0,k) == s.substr(i-k+1,k))
                pi[i] = k;
    return pi;
}
Затем делаем следующую строку
C++
1
s=a+'#'+b;
a-это то,ЧТО мы ищем
b-это то,В ЧЕМ мы ищем.
+ - конкатация
# - любой символ, которого нет ни в a, ни в b

Найдем префикс фунцию от этой строки.
Пусть длина a будет n, а b - m.
Тогда

C++
1
2
3
4
5
6
7
8
9
for(int i=n;i<n+m+1;i++)
    {
    if(pi[i]==n)
        {
        cout<<"YES"<<endl
        return 0;
        }
    }
    cout<<"NO"<<endl;
Добавлено через 19 секунд
pi - это вектор с префикс функии строки s
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 19:41  [ТС]     Поиск подстроки #9
alsav22, Да, я теперь понял, что это другая программа. А как мне реализовать проверку в своем коде?
Я понимаю, что функция
C++
1
search(a,b)
в строке
C++
1
if(search(a,b) == )
должна чему то равняться, но чему - не понимаю.
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
06.06.2014, 19:44     Поиск подстроки #10
Sh@dow777,

C++
1
2
3
4
5
6
7
if(search(a,b) != NULL)
    {
    cout<<"YES"<<endl;
     }
     else {
     cout<<"NO"<<endl;
     }
Добавлено через 43 секунды
Только вот strstr работает за O(N*M) где n и m длины строк, а алгоритм КМП за O(N+M)
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 20:01  [ТС]     Поиск подстроки #11
grikukan, Спасибо, но я пишу на Си. Реализацию алгоритма КМП на Си я взял отсюда(в том числе и вычисление префикс функции от строки) http://ru.wikibooks.org/wiki/%D0%9F%...82%D1%82%D0%B0. Осталось только проверку додумать.

Добавлено через 1 минуту
grikukan, Спасибо. Сейчас попробую.

Добавлено через 6 минут
grikukanВот весь код.
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
int search(char a[], char b[]){
    int i, j, n, m;
    n = strlen(a);
    m = strlen(b);
    int *c = (int*)malloc(m*sizeof(int));
 
    c[0] = 0;
    for(i = 1, j = 0; i < m;i++)
    {
        while(j > 0 && b[j] != b[i])
            j = c[j-1];
        if(b[j] == b[i])
            j++;
        c[i] = j;
 
        for(i = 0,j = 0;i < n;i++){
            while(j > 0 && b[j] != a[i])
                j = c[j-1];
            if(b[j] == a[i]);
            j++;
            if(j == m)
            {
                free(c);
                return i-j+1;
            }
        }
        free(c);
        return -1;
    }
}
 
int main()
{
    char a[1000000];
    char b[1000000];
 
    scanf("%s", a);
    scanf("%s", b);
 
    if(search(a,b) != 0)
        printf("YES");
    else
        printf("NO");
    getch();
 
    return 0;
}
Выводит ошибку "Stack Overflow".
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 20:04     Поиск подстроки #12
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Выводит ошибку "Stack Overflow".
Для чего такой размер массивов? Где вы такие строки видели?
C++
1
2
char a[1000000];
char b[1000000];
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 20:25  [ТС]     Поиск подстроки #13
alsav22, В задаче пределы длин строк 1<= A,B <= 1000000

Добавлено через 19 минут
alsav22, Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"?
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
06.06.2014, 20:47  [ТС]     Поиск подстроки #14
фллекс27, Это что?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 22:37     Поиск подстроки #15
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"?
Я уже сказал: массивы большие.
ValeryS
Модератор
6373 / 4839 / 440
Регистрация: 14.02.2011
Сообщений: 16,038
06.06.2014, 22:43     Поиск подстроки #16
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
В задаче пределы длин строк 1<= A,B <= 1000000
итого ты выделяешь в стеке 2 мегаБайта памяти , а стек то не резиновый
вывод или выделяй память динамически, и это правильно
или делай массивы глобальными, что не приветствуется

Добавлено через 52 секунды

Не по теме:

а вообще строка на 400 страниц это круто
тем более подстрока

Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
07.06.2014, 01:01  [ТС]     Поиск подстроки #17
ValeryS, Спасибо. Динамическое выделение памяти помогло. Но теперь другая проблема. Вот мой код.
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
int search(char a[], char b[]){
    int i, j, n, m;
    n = strlen(a);
    m = strlen(b);
    int *c = (int*)malloc(m*sizeof(int));
 
    c[0] = 0;
    for(i = 1, j = 0; i < m;i++)
    {
        while(j > 0 && b[j] != b[i])
            j = c[j-1];
        if(b[j] == b[i])
            j++;
        c[i] = j;
 
        for(i = 0,j = 0;i < n;i++){
            while(j > 0 && b[j] != a[i])
                j = c[j-1];
            if(b[j] == a[i]);
            j++;
            if(j == m)
            {
                free(c);
                return i-j+1;
            }
        }
        free(c);
        return -1;
    }
}
 
int main()
{
    char *a = new char[1000000];
    char *b = new char[1000000];
 
    scanf("%s", a);
    scanf("%s", b);
 
    if(search(a,b) != 0)
        printf("YES");
    else
        printf("NO");
    getch();
 
    return 0;
}
Я ввожу строку abaa и подстроку ab и выводит NO. Как мне правильно сделать проверку на наличие подстроки в строке?
Kerry_Jr
Модератор
 Аватар для Kerry_Jr
1855 / 1651 / 574
Регистрация: 14.05.2014
Сообщений: 4,726
Записей в блоге: 1
Завершенные тесты: 5
07.06.2014, 01:21     Поиск подстроки #18
раз уж вы используете библиотеку <string.h>, то почему бы не использовать вариант, который вам подсказали:
C++
1
2
3
4
char* search(char a[], char b[])
{
    return strstr(a, b);
}
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
07.06.2014, 01:27  [ТС]     Поиск подстроки #19
Kerry_Jr, Я уже писал в предыдущих постах, что мне нужно реализовать в программе алгоритм КМП. А это ведь другой способ поиска подстроки
C++
1
2
3
4
char* search(char a[], char b[])
{
    return strstr(a, b);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2014, 07:41     Поиск подстроки
Еще ссылки по теме:

C++ Поиск подстроки
Поиск подстроки C++
Поиск подстроки C++

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6373 / 4839 / 440
Регистрация: 14.02.2011
Сообщений: 16,038
07.06.2014, 07:41     Поиск подстроки #20
ну ежли ты построчно прокомментируешь свою функцию search то может и смогу помочь, а то я несколько заблудился
а может и сам найдешь ошибку при подробном комментировании
Yandex
Объявления
07.06.2014, 07:41     Поиск подстроки
Ответ Создать тему
Опции темы

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