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

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

01.12.2017, 16:54. Просмотров 656. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.12.2017, 16:54
Ответы с готовыми решениями:

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

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

Как написать регулярное выражение для выдергивания английских букв и символов: "+", ",", ":", "-", " ", "!", "?" и "."
Не могу ни как собразить как написать регулярное выражение для выдергивания английских букв и...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;,...

__________________
Помогаю в написании студенческих работ здесь.
3
Модератор
2767 / 1923 / 418
Регистрация: 26.03.2015
Сообщений: 7,142
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
0 / 0 / 0
Регистрация: 01.12.2017
Сообщений: 2
02.12.2017, 14:22  [ТС] 3
Как это будет на СИ?
Получается мне надо во 2 цикл к условию когда сравнивается следующая буква строки с шаблоном добавить условие str[i+j] == '*' или другой символ?
Немного не могу понять с++
0
Модератор
2767 / 1923 / 418
Регистрация: 26.03.2015
Сообщений: 7,142
02.12.2017, 15:44 4
Цитата Сообщение от zaza343434 Посмотреть сообщение
Как это будет на СИ?
Если у Вас вопрос по Си, то лучше его задать в разделе по Си.
Мне в Вашем коде не нравится то, что у Вас всё смешано в кучу. Каждая функция должна заниматься чем-то одним.

Если в шаблоне может встречаться только один спецсимвол, то код можно упростить.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2017, 15:44

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Получить значение из {"text1":"val1","text2":"val2","text3":{"text":"val"}}
Есть такая строка var my = '{&quot;text1&quot;:&quot;val1&quot;,&quot;text2&quot;:&quot;val2&quot;,&quot;text3&quot;:{&quot;text&quot;:&quot;val&quot;}}'; Как из...

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов), которые разделяются...

Известны сорта роз, выращиваемых тремя цветоводами: "Анжелика", "Виктория", "Гагарин", "Ave Maria", "Катарина", "Юбилейн
Известны сорта роз, выращиваемых тремя цветоводами: &quot;Анжелика&quot;, &quot;Виктория&quot;, &quot;Гагарин&quot;, &quot;Ave...

Написать программу проверки правильности написания сочетаний "жи", "ши", "ча", "ща", "чу", "щу". Исправить ошибки
дан текст.написать программу проверки правильности написания сочетаний &quot;жи&quot;, &quot;ши&quot;, &quot;ча&quot;, &quot;ща&quot;,...


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

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

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