Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
Гурген
13 / 0 / 1
Регистрация: 16.11.2014
Сообщений: 42
1

Реализовать поиск подстрок с помощью недетерминированного конечного автомата

03.06.2015, 21:38. Просмотров 1099. Ответов 1
Метки нет (Все метки)

Всем привет!Сразу к сути задачи.Необходимо реализовать поиск подстрок с помощью недетерминированного конечного автомата. Вообще не представляю с чего начать. Я так понял нужно НКА привести к ДКА и осуществить поиск подстрок. Прогуглил и нашел реализацию, но занимает порядка 1500 строк, не верю, что все так сложно. Может кто-то уже сталкивался с этим.Нужна ваша помощь.
Нашел реализацию на паскале с помощью ДКА(переделать не составит труда,но суть в том,что нужно через НКА)
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2015, 21:38
Ответы с готовыми решениями:

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

Реализация работы конечного автомата
Задача: Построить конечный автомат, проверяющий есть ли во входной цепочке S...

Создать программу конечного автомата
Создать программу этого асинхронного автомата. Помогите кто может

Алгоритм нахождения минимального конечного автомата
данный алгоритм уже давно известен, а мне нужен его код на с++. Не хотелось бы...

Построение конечного автомата по регулярной грамматике
G=({S, C, D}, {0, 1}, P, S) P: 1) S→1C | 0D; 2) C→0D | 0S | 1; 3) D→1C |...

1
Гурген
13 / 0 / 1
Регистрация: 16.11.2014
Сообщений: 42
07.06.2015, 18:28  [ТС] 2
Лучший ответ Сообщение было отмечено Гурген как решение

Решение

Вопос решен,тему закрывайте.
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// TIMP_avtomat.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <conio.h>
#include <math.h>
using namespace std;
const int maxplen=401;
bool hasch[256];
void computefunc(const string p, int f[maxplen][256])
{
    int m=p.length();
    for(int i=0;i<=m;i++)
    {
        for(int j=1;j<=255;j++)
        {
            if(hasch[j]) {
                int k=0;
                if(m>=i+1) k=i+1;
                else k=m;
                while(k>0)
                {
                    k=k-1;
                    char c=p[k];
                    if((k>=0)&&c==j){
                        int t1=k,t2=i;
                        while((t1>0)&&(p[t1]==p[t2])){
                            t1=t1-1;
                            t2=t2-1;
                        }
 
                        if(t1==0) {
                            k++;
                            break;  
                        }
                    }
 
                }
                f[i][j]=k;
            }
 
        }
    }
}
void match(const string t,int f[maxplen][256],const int m)
{
    cout<<"Осуществим проход по тексту. В начале автомат находится в состоянии q=0."<<endl;
    cout<<"Взяв следующий символ 'а' текста T. Автомат переходит в состояние f[q]['а']"<<endl<<endl;
    int n=t.length();
    int v=0,q=0;
    for (int i=0;i<n;i++){
        char c=t[i];
        v=f[q][c];
        cout<<"T["<<i+1<<"] =  "<<"'"<<t[i]<<"'"<<" , f["<<q<<", "<<"'"<<t[i]<<"'"<<"] = "<<v;
        q=f[q][c];
        if(v==m) cout<<", мы попали в состояние "<<m<<". следовательное образец входит в текст с позиции "<<i-m+2<<"."<<endl;
        else cout<<endl;
 
 
    }
 
 
 
}
void fill(const int n,const char ch)
{
    for(int i=0;i<=n;i++) cout<<ch;
}
void printfunc(int f[maxplen][256], const int m)
{
    cout<<endl;
    cout<<"Длина образца |P| = "<<m<<", поэтмоу количество состояний в автомате - "<<m+1<<" (|P|+1)."<<endl;
    cout<<"Автомат находит вхождения образца, если он попадает в допускающее состояние "<<m<<"."<<endl;
    cout<<"Построим функцию перехода f. Для каждого префикса P[0..m], где m=0.."<<m<<" ."<<endl;
    cout<<"Переберем все символы 'a', встречающиеся в образце, и найдем максимальный"<<endl<<"суффикс строки P[0..m]a, который является префиксом P. Длину найденного префикса"<<endl<<
"сохраним в ячейке f[m, 'a'] функции переходов."<<endl<<endl<<"Полученная в результате функция переходов имеет вид:"<<endl<<endl;
    int t=m;
    int digits=0;
    while(t>0){
        digits=digits;
        t=t/10;
 
    }
    cout<<"  ";
    for(int i=0;i<=m+digits;i++) cout<<"| "<<i;
    cout<<endl;
    for(int i=1;i<=255;i++){
        if(hasch[i])
        {
            cout<<"--";
            for(int j=0;j<=m;j++)
            {
                cout<<"+";
                fill(digits+1,'-');
            }
            cout<<endl;
            char c=i;
            cout<<" "<<c;
            for(int j=0;j<=m;j++) cout<<"| "<<f[j][i];
            cout<<endl;
        }
    }
        cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{ 
     setlocale(LC_ALL, "Russian");
    int f[maxplen][256];
    string t;
    cout<<"Введите строку:"<<endl;
    getline ( std::cin, t );
    int n=0;
    cout<<"Количество подстрок,которые мы пытаемся найти:"<<endl;
    cin>>n;
    string *p=new string[n];
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
        for(int i=0;i<n;i++)
        {
            memset(f, 0, sizeof(f));
            memset(hasch,false,sizeof(hasch));
            cout<<endl<<"Ищем образец \""<<p[i]<<"\" (P) в тексте "<<t<<"\" (T).";
            for(int j=0;j<p[i].length();j++) 
            {
                char c=p[i][j];
                hasch[c]=true;
            }
            computefunc(p[i],f);
            printfunc(f,p[i].length());
            match(t,f,p[i].length());
            cout<<"\n\n\n\n\n\n\n\n\n";
        }
    getch();
 
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2015, 18:28

Удаление пробелов перед знаками препинания (нарисовать диаграмму конечного автомата)
Удаление пробела, если он стоит перед запятой, точкой, точкой и запятой,...

Конечный автомат(Разработать граф переходов конечного автомата для выделения в тексте исходной программы на С++ комментариев)
Помогите решить задачку Разработать граф переходов конечного автомата для...

Поиск подстрок
Задание подсчитать все подстроки с использованием функции strstr(). Делаю так:...


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

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

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