Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.63
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
#1

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

06.06.2014, 14:49. Просмотров 1362. Ответов 36
Метки нет (Все метки)

Привет всем. Я пишу программу для поиска подстроки. Если подстрока есть в строке, вывести 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. Я прав?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2014, 14:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск подстроки (C++):

Мне надо сделать поиск последнего вхождения подстроки s1 в строку s(с функцией LastPos, не strstr). В этом коде просто вхождение подстроки в строку. - C++
#include &lt;stdio.h&gt; int count_of_substrings(string s, string s1){ int start = 0; int count = 0; int pos = 0; ...

Поиск подстроки - C++
Как считать из файла поочерёдно подстроку и искать её в строке? И почему то в итоге не корректно выводится результат 2 -х значений. Вот...

Поиск подстроки - C++
Эта программа написана чтобы искало буквы....а как написать чтобы искало количество слова например &quot; kag &quot; #include&lt;iostream.h&gt; ...

Поиск подстроки - C++
Почему при поиске вхождения подстроки в строку если я ввожу несколько слов, то компилятор разделяет строку на слова и ищет вхождение в них?...

Поиск подстроки - C++
Всем привет. Вот такое вот дали задание: найти все вхождения данного образца в строке. При этом надо указать индекс в тексте с которого...

Поиск подстроки - C++
Подскажите, как в тексте типа этого - &quot;101011110101001001001111010101010101100110&quot;, найти определенную комбинацию...

36
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-й строчки
0
alsav22
5426 / 4821 / 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);
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
06.06.2014, 18:17  [ТС] #4
alsav22, Спасибо. Теперь аргументы не подчеркивает. Не подскажете, как теперь сделать проверку на наличие подстроки в строке? Индекс начала подстроки в строке - это i-j+1?

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

Добавлено через 37 минут
Вопрос еще в силе. Скажите, как теперь сделать проверку на наличие подстроки в строке? Никак не могу понять.
0
alsav22
5426 / 4821 / 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;
}
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
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".
0
alsav22
5426 / 4821 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 19:14 #7
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Это дополнение к моей программе?
Нет. Это:
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
как теперь сделать проверку на наличие подстроки в строке?
0
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
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
06.06.2014, 19:41  [ТС] #9
alsav22, Да, я теперь понял, что это другая программа. А как мне реализовать проверку в своем коде?
Я понимаю, что функция
C++
1
search(a,b)
в строке
C++
1
if(search(a,b) == )
должна чему то равняться, но чему - не понимаю.
0
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)
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
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".
0
alsav22
5426 / 4821 / 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];
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
06.06.2014, 20:25  [ТС] #13
alsav22, В задаче пределы длин строк 1<= A,B <= 1000000

Добавлено через 19 минут
alsav22, Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"?
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
06.06.2014, 20:47  [ТС] #14
фллекс27, Это что?
0
alsav22
5426 / 4821 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.06.2014, 22:37 #15
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Так вы скажете мне, почему у меня выводит ошибку "Stack Overflow"?
Я уже сказал: массивы большие.
0
06.06.2014, 22:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2014, 22:37
Привет! Вот еще темы с ответами:

Поиск подстроки - C++
Всем добрый день, подскажите хорошая ли идея искать наличие подстроки таким способом, 8 строка. #include &lt;iostream&gt; #include &lt;string&gt; ...

Поиск подстроки - C++
Народец))) Подскажите пожалуйста новичку,как найти подстроку в строке?

Поиск подстроки в строке - C++
Добрый вечер. Помогите пожалуйста с заданием, нужно срочно его сделать. Сам текст: даны 2 массива (один большой, другой маленький), нужно...

Поиск подстроки в строке - C++
Найти множество всех слов, которые встречаются в каждом из 2 заданных предложений.


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru