Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/27: Рейтинг темы: голосов - 27, средняя оценка - 4.67
K-2
4 / 4 / 1
Регистрация: 15.05.2010
Сообщений: 38
1

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

15.05.2010, 10:10. Просмотров 4936. Ответов 5
Метки нет (Все метки)

При запуске программы пользователь вводит две строки текста, каждая не длинее 1024 символа. Нужно вывести индексы всех вхождений второй строки в первую, используя алгоритм Бойера-Мура.
Программу я написал, но она не хочет работать, не могу отладить...


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 <stdio.h>
#include <string.h>
#define MAX 1023
 
int search_for_boyermoore(char first_line[MAX], char second_line[MAX]){
    int table_shift[256];
    int i;
    int j;
    int k;
    int length_of_the_first_line;
    int length_of_the_second_line;
 
    length_of_the_first_line = strlen(first_line);
    length_of_the_second_line = strlen(second_line);
 
    for (i=0; i<256; i++){
        table_shift[i] = length_of_the_first_line;
    }
    for (i=0; i<length_of_the_first_line-1; i++){
      table_shift[second_line[i]] = length_of_the_first_line-i-1;
    }
 
    for(i=length_of_the_first_line-1; i<length_of_the_second_line; i+=table_shift[first_line[i]]) {
        j = length_of_the_first_line-1; 
        k = i;   
        while ((j>=0)&&(second_line[j] == first_line[k])){
            k--;
            j--; 
        }
        if (j<0){
            return k+1;
        }
    }
    printf("%d", k);
    return -1;
}
 
int main (){
    char first_line[MAX];
    char second_line[MAX];
 
    printf("%s\n","Enter the first line...");
    scanf("%s/n", &first_line);
 
    printf("%s\n","Enter the second line");
    scanf("%s/n", &second_line);
 
    search_for_boyermoore(first_line[MAX], second_line[MAX]);
    return 0;
}

Visual Microsoft Studio выдает 8 предупреждений...
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2010, 10:10
Ответы с готовыми решениями:

Поиск подстроки в строке
Нужно сделать поиск подстроки в строке на С. Без использования встроенной...

Поиск подстроки в строке
есть код, только я не очень понимаю как он работает P.S. считает сколько раз...

Поиск подстроки в строке
помогите пожалуйста написать без string

Поиск подстроки в строке
Здравствуйте! Необходимо выполнить следующее задание. В заданной строке найти...

Поиск подстроки в строке
Задача заключается в том, что есть один массив, состоящий из &quot;ab cd ef&quot; и есть...

5
shaurma
0 / 0 / 0
Регистрация: 29.11.2017
Сообщений: 1
15.05.2010, 15:12 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
using namespace std;
int main()
{
        string a,b;
        getline(cin,a);
        getline(cin,b);
 
        if( a.find(b, 0) != string::npos )
        cout << "строка b находится в a" << endl;
        else if(b.find(a, 0) != string::npos)
        cout << "строка a находится в b" << endl;
        else
        cout<<"net variantov";
        char zz;
        cin>>zz;
        return 0;
}
находит заданную подстроку в другой строке...
0
K-2
4 / 4 / 1
Регистрация: 15.05.2010
Сообщений: 38
18.05.2010, 10:13  [ТС] 3
круто конечно
но мне нужно понять что у меня не правильно...

Добавлено через 1 минуту
и на си...
0
-Xeon-
2 / 2 / 0
Регистрация: 15.02.2010
Сообщений: 26
18.05.2010, 10:37 4
K-2, Ну во первых нужно объявить прототип так int search_for_boyermoore(char *first_line, char *second_line), и вызывать так search_for_boyermoore(first_line, second_line);.

Добавлено через 20 секунд
И ошибок нет! По коду ща гляню.

Добавлено через 16 минут
Глянь это:
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <string.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define CHAR_MAX 1024
 
/* Вход: needle+nlen - что искать
 *   offset - позиция конца суффикса; suffixlen - его длина
 * Выход: 1, если есть совпадение суффикса (и нет совпадения более длинного суффикса)
 */
static int suffix_match(const char *needle, size_t nlen, size_t offset, size_t suffixlen)
{
    if (offset > suffixlen)
        return needle[offset - suffixlen - 1] != needle[nlen - suffixlen - 1] &&
            memcmp(needle + nlen - suffixlen, needle + offset - suffixlen, suffixlen) == 0;
    else
        return memcmp(needle + nlen - offset, needle, offset) == 0;
}
 
static int max(int a, int b)
{
    return a > b ? a : b; 
}
 
/* Вход: haystack - где искать, needle - что искать.
 *   hlen - длина haystack, nlen - длина needle
 * Выход: указатель на первое вхождение needle в haystack, либо NULL
 */
const char* memmem_boyermoore
    (const char* haystack, int hlen,
     const char* needle,   int nlen)
{
    int skip[1024];          /* Таблица суффиксов */
    int occ[CHAR_MAX + 1]; /* Таблица стоп-символов */
 
    if(nlen > hlen || nlen <= 0 || !haystack || !needle) 
        return NULL;
 
    /* ПОСТРОЕНИЕ ТАБЛИЦЫ СТОП-СИМВОЛОВ */
 
    /* Заполняем -1 (в Си нумерация символов с 0!!) */
    for(size_t a=0; a<CHAR_MAX+1; ++a)
        occ[a] = -1;
 
    /* В таблицу occ записывается последнее вхождение в needle  */
    /* (исключая последний символ) */
    for(size_t a = 0; a < nlen - 1; ++a) 
        occ[needle[a]] = a;
 
    /* ПОСТРОЕНИЕ ТАБЛИЦЫ СУФФИКСОВ */  
    /* Упрощённый вариант. Можно реализовать быстрее. */
    for(size_t a = 0; a < nlen; ++a)
    {
        size_t offs = nlen;
        while(offs && !suffix_match(needle, nlen, offs, a))
            --offs;
        skip[nlen - a - 1] = nlen - offs;
    }
 
    /* ПОИСК */
    for(size_t hpos = 0; hpos <= hlen - nlen; )
    {
        size_t npos = nlen - 1;
        /* Сверка needle и haystack с конца */
        while(needle[npos] == haystack[npos + hpos])
        {
            if(npos == 0) 
                return haystack + hpos;
 
            --npos;
        }
        /* Не совпало! */
        hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
        /*          ^^^         ^^^^                               */
        /*        суффикс     стоп-символ                          */
    }
    return NULL;
}
 
int main (){
        char first_line[CHAR_MAX];
        char second_line[CHAR_MAX];
 
        printf("%s\n","Enter the first line...");
        scanf("%s/n", &first_line);
 
        printf("%s\n","Enter the second line");
        scanf("%s/n", &second_line);
 
        //memmem_boyermoore(first_line, strlen(first_line), second_line, strlen(second_line));
 
        printf("\r\n%s", memmem_boyermoore(first_line, strlen(first_line), second_line, strlen(second_line)));
 
        getch();
 
        return 0;
}
Здесь функция возвращает какраз строку с того места с которого начинается вторая строка, т.е. можно узнать индекс в массиве.
1
K-2
4 / 4 / 1
Регистрация: 15.05.2010
Сообщений: 38
18.05.2010, 11:39  [ТС] 5
спасибо, ейчас попробую разобраться...
0
K-2
4 / 4 / 1
Регистрация: 15.05.2010
Сообщений: 38
29.05.2010, 10:39  [ТС] 6
вобщем я что-то намудрил...
программа запускается, все вводится... и выдает -858993460.... т.е. как я понимаю минимальный "size_t"...
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
#include <stdio.h>
#include <string.h>
#define MAX 1023
 
size_t search_for_boyermoore(char first_line[MAX], char second_line[MAX]){
    size_t table_shift[1023];
    size_t i;
    size_t j;
    size_t k;
    size_t length_of_the_first_line;
    size_t length_of_the_second_line;
 
    length_of_the_first_line = strlen(first_line);
    length_of_the_second_line = strlen(second_line);
 
    for (i=0; i<1023; i++){
        table_shift[i] = length_of_the_first_line;
    }
    for (i=0; i<length_of_the_first_line-1; i++){
      table_shift[(unsigned char)first_line[i]] = length_of_the_first_line-i-1;
    }
            
    for(i=length_of_the_first_line-1; i<length_of_the_second_line; i+=table_shift[second_line[i]]) {
        j = length_of_the_first_line-1;
        k = i;
        while ((j>=0)&&(first_line[j] == second_line[k])){
            k--;
            j--;
 
        }
        if (j<0){
            return k+1;
        }
 
    }
    printf("%d\n",k);
    return -1;
}
 
int main (){
    char first_line[MAX];
    char second_line[MAX];
 
    printf("%s\n","Enter the first line...");
    scanf("%s", &first_line);
 
    printf("%s\n","Enter the second line");
    scanf("%s", &second_line);
 
    search_for_boyermoore(first_line, second_line);
 
    return 0;
}
0
29.05.2010, 10:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2010, 10:39

Поиск подстроки в строке с маской
Суть вот в чем: дан текст и маска. Маска содержит буквы и символ заполнитель *,...

Как осуществить поиск подстроки в строке?
Как осуществить поиск подстроки в строке на языке С ??

Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку
Выполнить поиск подстроки внутри данной строки,замену найденной подстроки на...


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

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

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