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

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

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

Привет всем. Я пишу программу для поиска подстроки. Если подстрока есть в строке, вывести YES. Иначе - NO.
Вот код(еще не дописанный)

C++

#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. Я прав?

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

ValeryS, Я взял пример с этого кода

C++

int seek_substring_KMP (char s[], char p[])
{
    int i, j, N, M;
    N = strlen(s);
    M = strlen(p);
    int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
    /* Вычисление префикс-функции */
    d[0]=0;
    for(i=1,j=0;i<M;i++)
    {
        while(j>0 && p[j]!=p[i])
            j = d[j-1];
        if(p[j]==p[i])
            j++;
        d[i]=j;
    }
    /* поиск */
    for(i=0,j=0;i<N; i++)
    {
        while(j>0 && p[j]!=s[i])
            j=d[j-1];
        if(p[j]==s[i])
                        j++;
        if (j==M)
                {
                free (d); /* освобождение памяти массива d */
                        return i-j+1;
                }
    }
        free (d); /* освобождение памяти массива d */
    return -1;
}

Добавлено через 1 минуту
ValeryS, Просто переименовал массивы и их размеры.

@Sh@dow777 · 15.06.2014, 04:52 **[ТС]**

Извините, что поднимаю тему. В общем, я изменил проверку на наличие подстроки в строке. Вот код.

C++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
int i, j, n, m;
 
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) == i-j+1)
        printf("YES");
    else
        printf("NO");
 
    delete[]a;
    delete[]b;
 
    getch();
 
    return 0;
}

Теперь если подстрока не входит в строку, выводит NO. Но если я ввожу строку astr и подстроку tt, выводит YES. Хотя не должно. Что мне нужно исправить?

Добавлено через 12 часов 17 минут
Теперь я переделал весь код на С++, как сказал grikukan. Вот код.

C++

#include <iostream>
#include <vector>
#include <string>
#include <conio.h>
using namespace std;
    
string a;
string b;
string s;
 
vector<int>prefix(string s)
{
    s = b + '#' + a;
 
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j]) 
            ++j;
        pi[i] = j;
    }
    return pi;
}
 
int main()
{
    int k, l;
 
    k = a.length();
    l = b.length();
 
    getline(cin,a);
    getline(cin,b);
 
    for(int i = l;i < l+k+1;i++){
        if(pi[i] == l)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
    getch();
 
    return 0;
}

Но теперь в этой строке

C++

1	if(pi[i] == l)

мне подчеркивает pi. Скажите, что я не так делаю или не доделываю?

alsav22 · 15.06.2014, 05:30

Вектор pi объявлен в функции prefix(), в других функциях (main()) его не видно.

@Sh@dow777 · 15.06.2014, 16:37 **[ТС]**

alsav22, Вот так нужно сделать?

C++

int main()
{
    int k, l;
    vector<int>pi;
 
    k = a.length();
    l = b.length();
 
    getline(cin,a);
    getline(cin,b);
 
    for(int i = l;i < l+k+1;i++){
        if(pi[i] == l)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
    getch();
 
    return 0;
}

Выводит ошибку "Debug Assertion Failed". Дело в том, что с векторами я сталкиваюсь впервые. Пытаюсь разобраться по ходу дела. А программу нужно сдать через 2 дня.

alsav22 · 15.06.2014, 17:12

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

Выводит ошибку "Debug Assertion Failed"

К пустому вектору нельзя по индексу обращаться.

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

Вот так нужно сделать?

Чушь пишите.

@Sh@dow777 · 15.06.2014, 17:51 **[ТС]**

alsav22,

Сообщение от alsav22

К пустому вектору нельзя по индексу обращаться.

Как это понять? Объясните, пожалуйста, если вам не трудно.
Попробовал так.

C++

#include <iostream>
#include <vector>
#include <string>
#include <conio.h>
using namespace std;
 
int n;
string a;
string b;
string s;
 
vector<int>prefix(string s)
{
    s = b + '#' + a;
 
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j]) 
            ++j;
        pi[i] = j;
    }
    return pi;
}
 
int main()
{
    int k, l;
    vector<int>pi(n);
 
    k = a.length();
    l = b.length();
 
    getline(cin,a);
    getline(cin,b);
 
    for(int i = l;i < l+k+1;i++){
        if(pi[i] == l)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
    getch();
 
    return 0;
}

Все та же ошибка.

alsav22 · 15.06.2014, 18:26

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

Все та же ошибка.

Вектор всё так же пуст, поэтому и ошибка всё та же. Отладчиком умеете пользоваться?

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

Как это понять? Объясните, пожалуйста, если вам не трудно.

Что тут понимать?

Сообщение от alsav22

К пустому вектору нельзя по индексу обращаться.

@Sh@dow777 · 15.06.2014, 19:02 **[ТС]**

alsav22, Вот я изменил.

C++

#include <iostream>
#include <vector>
#include <string>
#include <conio.h>
using namespace std;
 
int n = 1000000;
string a;
string b;
string s;
 
vector<int>prefix(string s)
{
    s = b + '#' + a;
 
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j]) 
            ++j;
        pi[i] = j;
    }
    return pi;
}
 
int main()
{
    int k, l;
    vector<int>pi(n);
 
    k = a.length();
    l = b.length();
 
    getline(cin,a);
    getline(cin,b);
 
    for(int i = l;i < l+k+1;i++){
        if(pi[i] == l)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
    getch();
 
    return 0;
}

Вектор не пуст теперь. Но я ввожу строку aaaa и подстроку bb и мне выводит YES

alsav22 · 15.06.2014, 19:39

???

Сообщение от alsav22

Отладчиком умеете пользоваться?

@Sh@dow777 · 15.06.2014, 20:21 **[ТС]**

alsav22, С помощью отладчика нашел одну ошибку.
Вот этот кусочек

C++

1 2	k = a.length(); l = b.length();

я поставил перед

C++

1 2	getline(cin,a); getline(cin,b);

Это мой пролет. Но все равно выводит такой бред(изображение).
В векторе 1000000 нулей, я так понял.

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

Вопрос еще в силе. Скажите, что я делаю не так? Почему, когда я ввожу строку asfd и подстроку fd, мне 4 раза выводит NO?

alsav22 · 16.06.2014, 02:54

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

Скажите, что я делаю не так?

Всё.

@Sh@dow777 · 16.06.2014, 03:08 **[ТС]**

alsav22, Я ждал от вас такого ответа

Если серьезно, я следовал советам [nick]grirukan[nick]. И еще прочитал про алгоритм КМП на этом сайте http://e-maxx.ru/algo/prefix_function. Вроде все делаю правильно. Либо может мне не нужно сначала объединять строки и написать сразу так?

C++

vector<int>prefix(string s)
{
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j]) 
            ++j;
        pi[i] = j;
    }
    return pi;
}

А потом уже объединить строки

C++

1	s = b + '#' + a;

и заново вычислить префикс-функцию для этой строки?

alsav22 · 16.06.2014, 03:12

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

Я ждал от вас такого ответа

Я знаю, старался не обмануть ожиданий...

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

Если серьезно

Какое отношение функция prefix() имеет к тому, что делается в main()?

@Sh@dow777 · 16.06.2014, 03:31 **[ТС]**

alsav22, Функция prefix(), как я понимаю, вычисляет префикс-функцию строки s. Но я хочу понять, можно ли сразу объединить строки

C++

1	s = b + '#' + a;

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

И да, все таки с выводом 4-ех NO я разобрался, но все равно выводит неверный ответ

C++

#include <iostream>
#include <vector>
#include <string>
#include <conio.h>
using namespace std;
 
string a;
string b;
string s;
int n = 1000000;
 
vector<int>prefix(string s)
{
    s = b + '#' + a;
 
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j]) 
            ++j;
        pi[i] = j;
    }
    return pi;
}
 
int main()
{
    int k, l;
    vector<int>pi(n);
 
    getline(cin,a);
    getline(cin,b);
 
    k = a.length();
    l = b.length();
 
    for(int i = l;i < l+k+1;i++){
        if(pi[i] == l){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
 
    getch();
 
    return 0;
}

alsav22 · 16.06.2014, 03:37

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

Функция prefix(), как я понимаю, вычисляет префикс-функцию строки s.

???

Сообщение от alsav22

Какое отношение функция prefix() имеет к тому, что делается в main()?

@Sh@dow777 · 16.06.2014, 03:48 **[ТС]**

alsav22, Боже, вы мой кумир

Переделал так и сдал решение.

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
string a;
string b;
string s;
 
 
int main()
{
    int k, l;
 
    getline(cin,a);
    getline(cin,b);
 
    k = a.length();
    l = b.length();
 
    s = b + "#" + a;
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j]) 
            ++j;
        pi[i] = j;
    }
 
    for(int i = l;i < l+k+1;i++){
        if(pi[i] == l){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
 
    return 0;
}

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	15.06.2014, 05:30	23
	Вектор pi объявлен в функции prefix(), в других функциях (main()) его не видно. 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	15.06.2014, 17:12	25
	Сообщение от Sh@dow777 Выводит ошибку "Debug Assertion Failed" К пустому вектору нельзя по индексу обращаться. Сообщение от Sh@dow777 Вот так нужно сделать? Чушь пишите. 1

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	15.06.2014, 18:26	27
	Сообщение от Sh@dow777 Все та же ошибка. Вектор всё так же пуст, поэтому и ошибка всё та же. Отладчиком умеете пользоваться? Сообщение от Sh@dow777 Как это понять? Объясните, пожалуйста, если вам не трудно. Что тут понимать? Сообщение от alsav22 К пустому вектору нельзя по индексу обращаться. 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	15.06.2014, 19:39	29
	??? Сообщение от alsav22 Отладчиком умеете пользоваться? 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	16.06.2014, 02:54	32
	Сообщение от Sh@dow777 Скажите, что я делаю не так? Всё. 1

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	16.06.2014, 01:47 [ТС]	31
	Вопрос еще в силе. Скажите, что я делаю не так? Почему, когда я ввожу строку asfd и подстроку fd, мне 4 раза выводит NO? 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	16.06.2014, 03:12	34
	Сообщение от Sh@dow777 Я ждал от вас такого ответа Я знаю, старался не обмануть ожиданий... Сообщение от Sh@dow777 Если серьезно Какое отношение функция prefix() имеет к тому, что делается в main()? 1

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	16.06.2014, 03:37	36
	Сообщение от Sh@dow777 Функция prefix(), как я понимаю, вычисляет префикс-функцию строки s. ??? Сообщение от alsav22 Какое отношение функция prefix() имеет к тому, что делается в main()? 1