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
| // main.cpp
// 字符串匹配测试
//
// Created by Copriwolf on 15/10/21.
// Copyright 2015年 Copriwolf. All rights reserved.
//
#include <iostream>
using namespace std;
int Welcome(string& S, string& T,int &choose);
int SimplePatternMatching(string S, string T,int pos);
class KMP{
public:
int next[];
int KMP_Matching(string S,string T,int pos);
int KMP_NextArray(string S,string T,int pos);
};
int main(int argc, const char * argv[]) {
int choose=0;
int pos=0;
string S,T;
Welcome(S,T,choose);
switch (choose) {
case 1:
cout<<"简单匹配算法成功运行"<<endl;
cout<<"模式串在主串中第"<<SimplePatternMatching(S, T, pos);
cout<<"个字符之后的位置！"<<endl;
cout<<"///////////////////////////////"<<endl;
break;
case 2:{
cout<<"KMP匹配算法成功运行"<<endl;
KMP kmp;
kmp.KMP_NextArray(S, T, pos);
cout<<"模式串在主串中第"<<kmp.KMP_Matching(S, T, pos);
cout<<"个字符之后的位置！"<<endl;
cout<<"///////////////////////////////"<<endl;
break;
}
case 0:
exit(0);
default:
cout<<"Your input a wrong number!Please try again!";
cout<<"///////////////////////////////"<<endl;
break;
}
return 0;
}
//欢迎界面
int Welcome(string& S, string& T,int& choose){
cout<<"Welcome:)"<<endl;
cout<<"Please input the Original text:"<<endl;
S="";
getline(cin,S);
cout<<"Please input the Pattern text:"<<endl;
T="";
getline(cin,T);
cout<<"please select your choose:"<<endl;
cout<<"[1]简单匹配算法;[2]KMP匹配算法;[0]退出"<<endl;
cin>>choose;
return choose;
}
//简单匹配实现
int SimplePatternMatching(string S,string T,int pos){
int i=pos;
int j=0;
while ((i<= int(S.length()))&&(j<= int(S.length()))) {
if (S[i] == T[j]) {++i; ++j;}
else{i=i-j+2;j=1;}
}
if (j >int(T.length())) return (i-int(T.length()));
else return 0;
}
//KMP匹配实现
int KMP::KMP_Matching(string S,string T,int pos){
int i=pos;
int j=0;
while ((i<= int(S.length()))&&(j<= int(S.length()))) {
if (S[i] == T[j] || j==0) {++i; ++j;}
else{
j= next[j];
}
}
if (j >int(T.length())) return (i-int(T.length()));
else return 0;
}
int KMP::KMP_NextArray(string S,string T,int pos){
int i=pos;
int j=1;
while ((i <= int(T.length()))&& (j <= int(T.length()))) {
if (j ==0 || int(T.length()) == int(S.length())) {
++i;
++j;
}
else{
j=next[j];
}
}
if (j >int(T.length())) {
return (i-int(T.length()));
}
else{
return 0;
}
}
|