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

@zaza343434 · Регистрация: 01.12.2017

Добрый день

Имею такое задание:
необходимо написать программу, которая сможет найти в файле строку и вывести ее, где содержится заданный шаблон (аргумент из командной строки). Например: имею шаблон "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

#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 раз.

@Shamil1 · 01.12.2017, 18:33

Как-то так:

C#

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#

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);
}

@zaza343434 · 02.12.2017, 14:22 **[ТС]**

Как это будет на СИ?
Получается мне надо во 2 цикл к условию когда сравнивается следующая буква строки с шаблоном добавить условие str[i+j] == '*' или другой символ?
Немного не могу понять с++

@Shamil1 · 02.12.2017, 15:44

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

Как это будет на СИ?

Если у Вас вопрос по Си, то лучше его задать в разделе по Си.
Мне в Вашем коде не нравится то, что у Вас всё смешано в кучу. Каждая функция должна заниматься чем-то одним.

Если в шаблоне может встречаться только один спецсимвол, то код можно упростить.

@zaza343434 0 / 0 / 0 Регистрация: 01.12.2017 Сообщений: 2
	02.12.2017, 14:22 [ТС]	3
	Как это будет на СИ? Получается мне надо во 2 цикл к условию когда сравнивается следующая буква строки с шаблоном добавить условие str[i+j] == '*' или другой символ? Немного не могу понять с++ 0

@Shamil1 Модератор 2767 / 1923 / 418 Регистрация: 26.03.2015 Сообщений: 7,142
	02.12.2017, 15:44	4
	Сообщение от zaza343434 Как это будет на СИ? Если у Вас вопрос по Си, то лучше его задать в разделе по Си. Мне в Вашем коде не нравится то, что у Вас всё смешано в кучу. Каждая функция должна заниматься чем-то одним. Если в шаблоне может встречаться только один спецсимвол, то код можно упростить. 0

Опции темы