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

@Sh@dow777 · Регистрация: 10.12.2013

Студворк — интернет-сервис помощи студентам

Привет всем. Я пишу программу для поиска подстроки. Если подстрока есть в строке, вывести 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 · 06.06.2014, 16:18

Как вы объявляете a и b, которые передаете функции в первом варианте?

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

P.S. 1) У вас не проинициализирована переменная j. 2) В цикле (15-16 строки) не меняется счетчик цикла, т.е. можете бесконечно проверять условие для одного элемента. То же самое в 22-23 строках. 3) вам не нужен цикл из 13-й строчки

alsav22 · 06.06.2014, 16:25

C++
1
2
3
4
char a[1000000];
char b[1000000];
...
search(a,b);

@Sh@dow777 · 06.06.2014, 18:17 **[ТС]**

alsav22, Спасибо. Теперь аргументы не подчеркивает. Не подскажете, как теперь сделать проверку на наличие подстроки в строке? Индекс начала подстроки в строке - это i-j+1?

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

Добавлено через 37 минут
Вопрос еще в силе. Скажите, как теперь сделать проверку на наличие подстроки в строке? Никак не могу понять.

alsav22 · 06.06.2014, 18:33

Сообщение от 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 · 06.06.2014, 19:02 **[ТС]**

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 · 06.06.2014, 19:14

Сообщение от Sh@dow777

Это дополнение к моей программе?

Нет. Это:

Сообщение от Sh@dow777

как теперь сделать проверку на наличие подстроки в строке?

@grikukan · 06.06.2014, 19:35

Сделайте так:

Для начала надо научиться считать префикс-функцию от строки

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 · 06.06.2014, 19:41 **[ТС]**

alsav22, Да, я теперь понял, что это другая программа. А как мне реализовать проверку в своем коде?
Я понимаю, что функция

C++
1
search(a,b)

в строке

C++
1
if(search(a,b) == )

должна чему то равняться, но чему - не понимаю.

@grikukan · 06.06.2014, 19:44

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 · 06.06.2014, 20:01 **[ТС]**

grikukan, Спасибо, но я пишу на Си. Реализацию алгоритма КМП на Си я взял отсюда(в том числе и вычисление префикс функции от строки) http://ru.wikibooks.org/wiki/%... 1%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 · 06.06.2014, 20:04

Сообщение от Sh@dow777

Выводит ошибку "Stack Overflow".

Для чего такой размер массивов? Где вы такие строки видели?

C++
1
2
char a[1000000];
char b[1000000];

@Sh@dow777 · 06.06.2014, 20:25 **[ТС]**

alsav22, В задаче пределы длин строк 1<= A,B <= 1000000

Добавлено через 19 минут
alsav22, Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"?

@Sh@dow777 · 06.06.2014, 20:47 **[ТС]**

фллекс27, Это что?

alsav22 · 06.06.2014, 22:37

Сообщение от Sh@dow777

Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"?

Я уже сказал: массивы большие.

ValeryS · 06.06.2014, 22:43

Сообщение от Sh@dow777

В задаче пределы длин строк 1<= A,B <= 1000000

итого ты выделяешь в стеке 2 мегаБайта памяти , а стек то не резиновый
вывод или выделяй память динамически, и это правильно
или делай массивы глобальными, что не приветствуется

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

Не по теме:

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

@Sh@dow777 · 07.06.2014, 01:01 **[ТС]**

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 · 07.06.2014, 01:21

раз уж вы используете библиотеку <string.h>, то почему бы не использовать вариант, который вам подсказали:

C++
1
2
3
4
char* search(char a[], char b[])
{
    return strstr(a, b);
}

@Sh@dow777 · 07.06.2014, 01:27 **[ТС]**

Kerry_Jr, Я уже писал в предыдущих постах, что мне нужно реализовать в программе алгоритм КМП. А это ведь другой способ поиска подстроки

C++
1
2
3
4
char* search(char a[], char b[])
{
    return strstr(a, b);
}

ValeryS · 07.06.2014, 07:41

ну ежли ты построчно прокомментируешь свою функцию search то может и смогу помочь, а то я несколько заблудился
а может и сам найдешь ошибку при подробном комментировании

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Akelle 0 / 0 / 0 Регистрация: 06.06.2014 Сообщений: 5
	06.06.2014, 16:18
	Как вы объявляете a и b, которые передаете функции в первом варианте? Судя по коду, в случае нахождения подстроки функция должна возвращать индекс начала подстроки в строке. P.S. 1) У вас не проинициализирована переменная j. 2) В цикле (15-16 строки) не меняется счетчик цикла, т.е. можете бесконечно проверять условие для одного элемента. То же самое в 22-23 строках. 3) вам не нужен цикл из 13-й строчки 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	06.06.2014, 18:17 [ТС]
	alsav22, Спасибо. Теперь аргументы не подчеркивает. Не подскажете, как теперь сделать проверку на наличие подстроки в строке? Индекс начала подстроки в строке - это i-j+1? Добавлено через 2 минуты Я просто взял реализацию алгоритма отсюда http://ru.wikibooks.org/wiki/%... 1%82%D0%B0 Добавлено через 37 минут Вопрос еще в силе. Скажите, как теперь сделать проверку на наличие подстроки в строке? Никак не могу понять. 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	06.06.2014, 20:25 [ТС]
	alsav22, В задаче пределы длин строк 1<= A,B <= 1000000 Добавлено через 19 минут alsav22, Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"? 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	06.06.2014, 20:47 [ТС]
	фллекс27, Это что? 0

ValeryS Модератор 8979 / 6745 / 921 Регистрация: 14.02.2011 Сообщений: 23,856
	07.06.2014, 07:41
	ну ежли ты построчно прокомментируешь свою функцию search то может и смогу помочь, а то я несколько заблудился а может и сам найдешь ошибку при подробном комментировании 0