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;
} |
(
Сообщение было отмечено Гурген как решение
