Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
zaza343434
0 / 0 / 0
Регистрация: 01.12.2017
Сообщений: 2
1

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")

01.12.2017, 16:54. Просмотров 252. Ответов 3

Добрый день

Имею такое задание:
необходимо написать программу, которая сможет найти в файле строку и вывести ее, где содержится заданный шаблон (аргумент из командной строки). Например: имею шаблон "dvd" и файл, в котором несколько строк:
1 anbmd
2 advnm
3 udvdnm
4 dvujh

Проходит по каждой строке, находит совпадние с 3 строкой и выводит на экран: udvdnm
Я написал для этого код, все работает
Сравниваю в цикле символ строки с символом шаблона, если нахожу совпадение - запускаю 2 цикл, который уже сравнивает следующий символ строки с каждой последующим симоволом шаблона.

Но дальше его нужно усложнить. Шаблон может иметь в себе специальный символы (?, *, +), где ? - 0 или 1 символ, * - 0 или более символов, + - 1 или более символов. То есть по шаблону, например, "colou?r" он должен из списка:
color
colour
colouur
colouuur

вывести color, colour. И соотвественно также с другими символами.

Искал решение в интернете, пытался придумать что-то сам, но пока сделал только для ?, да и то как-то коряво, а как сделать для * и +, где может быть неопределенное число симоволов - не знаю. Подскажите примерный алгоритм поиска или код(сам пишу на СИ).

Заранее благодарю.

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
#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, char *argv[])
{
  if(argc == 3)
    {
        int pointer_file = 0;
        int pattern = 0;
        int kontrol = 0;
        char str[250];
        for(int i = 0; argv[1][i] != '\0'; i++)
        {
            pattern++; 
        }
        FILE *file;
        file = fopen(argv[2], "r"); // open file
        if(file == NULL)
        {
            fprintf(stderr, "Error: open file ’%s’.\n", argv[2]);
            return 100;
        }
        else
        {
            while( !(feof(file)) )
                {
                    int result = 0;
                    int length = 0;
                    fseek(file, pointer_file , SEEK_SET);
                     
                    for(int i = 0; ; i++)
                    {
                        fscanf(file, "%c", &str[i]);
                        if(str[i] == '\n')
                        {
                            str[i+1] = '\0';
                            break;
                        }
                        length = i;
                    }
                      
                    for(int i = 0; i < length; i++)
                    {
                        for(int j = 0; str[i+j] == argv[1][j]; j++)
                        {
                            if(j - pattern == -1)
                            {
                                result = 1;
                                kontrol = 1;
                                break;                      
                            }
                        }
                    }
                    
                    if(result == 1)
                    {
                        printf("%s", str);
                    }
                    for(int i = 0; i < length; i++)
                    {
                        str[i] = 0;
                    }
                    pointer_file += (length+1);
                }
        }
        fclose(file);
        if(kontrol == 0)
        {
            return 1;
        }
else
    {
        fprintf(stderr, "Error\n");
        return 1;
    }
  return 0;
}
Добавлено через 8 минут
Символ ?, *, + может встречаться в шаблоне максимально 1 раз.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2017, 16:54
Ответы с готовыми решениями:

Алгоритм роста "квадрата" или как работает "черный ящик"
Хочу спросить совета по нахождению формулы для &quot;черного ящика&quot;, который на входе принимает 2...

Из пункта "А" приехать в пункт "Б" и показать возможные траектории движения
Задача вот такая: надо из пункта &quot;А&quot; приехать в пункт &quot;Б&quot; и показать возможные траектории движения....

Критерии вхождения "шара" в "ящик"
Дано: Ящик (С параметрами: высота, длина, ширина), n шаров в этом ящике (С радиусами ri)....

Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?
Чем отличаются два понятия: &quot;Абстрактный тип данных&quot; и &quot;Структура данных&quot;?

Поиск максимального элемента в массиве методом "разделяй и властвуй"
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его...

3
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,505
01.12.2017, 18:33 2
Как-то так:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool SeachByMask(string text, string mask)
{
    mask = '*' + mask;
    Func<int, int, bool> search = null;
    search = (i, j) => 
    {
        if(j >= mask.Length) return true;
        if(i >= text.Length) return mask[j] == '*' && search(i, j + 1);
        
        switch(mask[j])
        {
            case '*': return search(i, j + 1) || search(i + 1, j);
            case '?': return search(i + 1, j + 1);
            default:  return text[i] == mask[j] && search(i + 1, j + 1);
        }
    }; 
    return search(0, 0);
}
Код не тестировал. Могут быть ошибки.


з.ы. Можно записать функцию одним булевым выражением, но код станет менее читабельным:
C#
1
2
3
4
5
6
7
8
9
10
bool SeachByMask2(string text, string mask)
{
    mask = '*' + mask;
    Func<int, int, bool> search = null;
    search = (i, j) => j >= mask.Length
        || mask[j] == '*' && search(i, j + 1)
        || i < text.Length && (mask[j] == '*' && search(i + 1, j) 
                               || (mask[j] == '?' || text[i] == mask[j]) && search(i + 1, j + 1));
    return search(0, 0);
}
0
zaza343434
0 / 0 / 0
Регистрация: 01.12.2017
Сообщений: 2
02.12.2017, 14:22  [ТС] 3
Как это будет на СИ?
Получается мне надо во 2 цикл к условию когда сравнивается следующая буква строки с шаблоном добавить условие str[i+j] == '*' или другой символ?
Немного не могу понять с++
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,505
02.12.2017, 15:44 4
Цитата Сообщение от zaza343434 Посмотреть сообщение
Как это будет на СИ?
Если у Вас вопрос по Си, то лучше его задать в разделе по Си.
Мне в Вашем коде не нравится то, что у Вас всё смешано в кучу. Каждая функция должна заниматься чем-то одним.

Если в шаблоне может встречаться только один спецсимвол, то код можно упростить.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2017, 15:44

Поиск частей внешнего контура по четырём сторонам с "захватом"
Вот так вот чудно я назвал тему =) Всем привет. В рамках проекта нужно придумать алгоритм поиска...

Поиск алгоритма перемещения стопки карт в "Свободной ячейке"
Добрый день, друзья. Споткнулись на поиске алгоритма определения последовательности перемещения...

Поиск максимального паросочетания в задаче "Испорченный паркет"
Привет всем! Прошу помощи. Есть задача &quot;Испорченный паркет&quot;. Условие задачи следующее: Пол в...


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

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

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