Форум программистов, компьютерный форум 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. Я прав?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
07.06.2014, 12:20  [ТС]     Поиск подстроки #21
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
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
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
15.06.2014, 04:52  [ТС]     Поиск подстроки #22
Извините, что поднимаю тему. В общем, я изменил проверку на наличие подстроки в строке. Вот код.
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
53
54
55
56
57
58
#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++
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
#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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
15.06.2014, 05:30     Поиск подстроки #23
Вектор pi объявлен в функции prefix(), в других функциях (main()) его не видно.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
15.06.2014, 16:37  [ТС]     Поиск подстроки #24
alsav22, Вот так нужно сделать?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
15.06.2014, 17:12     Поиск подстроки #25
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Выводит ошибку "Debug Assertion Failed"
К пустому вектору нельзя по индексу обращаться.
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Вот так нужно сделать?
Чушь пишите.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
15.06.2014, 17:51  [ТС]     Поиск подстроки #26
alsav22,
Цитата Сообщение от alsav22 Посмотреть сообщение
К пустому вектору нельзя по индексу обращаться.
Как это понять? Объясните, пожалуйста, если вам не трудно.
Попробовал так.
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
#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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
15.06.2014, 18:26     Поиск подстроки #27
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Все та же ошибка.
Вектор всё так же пуст, поэтому и ошибка всё та же. Отладчиком умеете пользоваться?
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Как это понять? Объясните, пожалуйста, если вам не трудно.
Что тут понимать?
Цитата Сообщение от alsav22 Посмотреть сообщение
К пустому вектору нельзя по индексу обращаться.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
15.06.2014, 19:02  [ТС]     Поиск подстроки #28
alsav22, Вот я изменил.
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
#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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
15.06.2014, 19:39     Поиск подстроки #29
???
Цитата Сообщение от alsav22 Посмотреть сообщение
Отладчиком умеете пользоваться?
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
15.06.2014, 20:21  [ТС]     Поиск подстроки #30
alsav22, С помощью отладчика нашел одну ошибку.
Вот этот кусочек
C++
1
2
k = a.length();
    l = b.length();
я поставил перед
C++
1
2
getline(cin,a);
    getline(cin,b);
Это мой пролет. Но все равно выводит такой бред(изображение).
В векторе 1000000 нулей, я так понял.
Изображения
 
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
16.06.2014, 01:47  [ТС]     Поиск подстроки #31
Вопрос еще в силе. Скажите, что я делаю не так? Почему, когда я ввожу строку asfd и подстроку fd, мне 4 раза выводит NO?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
16.06.2014, 02:54     Поиск подстроки #32
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Скажите, что я делаю не так?
Всё.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
16.06.2014, 03:08  [ТС]     Поиск подстроки #33
alsav22, Я ждал от вас такого ответа Если серьезно, я следовал советам [nick]grirukan[nick]. И еще прочитал про алгоритм КМП на этом сайте http://e-maxx.ru/algo/prefix_function. Вроде все делаю правильно. Либо может мне не нужно сначала объединять строки и написать сразу так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
16.06.2014, 03:12     Поиск подстроки #34
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Я ждал от вас такого ответа
Я знаю, старался не обмануть ожиданий...
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Если серьезно
Какое отношение функция prefix() имеет к тому, что делается в main()?
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
16.06.2014, 03:31  [ТС]     Поиск подстроки #35
alsav22, Функция prefix(), как я понимаю, вычисляет префикс-функцию строки s. Но я хочу понять, можно ли сразу объединить строки
C++
1
s = b + '#' + a;
и считать префикс-функцию уже для этой строки?

И да, все таки с выводом 4-ех 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
46
47
48
49
50
51
#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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
16.06.2014, 03:37     Поиск подстроки #36
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Функция prefix(), как я понимаю, вычисляет префикс-функцию строки s.
???
Цитата Сообщение от alsav22 Посмотреть сообщение
Какое отношение функция prefix() имеет к тому, что делается в main()?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.06.2014, 03:48     Поиск подстроки
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
16.06.2014, 03:48  [ТС]     Поиск подстроки #37
alsav22, Боже, вы мой кумир Переделал так и сдал решение.
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
#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;
}
Yandex
Объявления
16.06.2014, 03:48     Поиск подстроки
Ответ Создать тему
Опции темы

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