算法实验四 串匹配算法
董灏 Pb05210056
实验目的:实验中我们使用了四种方法进行串匹配,通过对相同的文本和相同的模式串进行
四种不同算法的串匹配操作,比较四种算法的优劣。
为了使实验中可以产生匹配,我们的字符集长度为 2。
实验数据:
如下表:
文本串长度
2
4
2
6
2
8
算法/模式串长度
4
8
2
2
6
12
2
4
8
16
2
6
Shift or
99
99
99
101
101
178
106
106
109
Horspool
92
91
94
179
93
97
109
118
110
Quick search
92
93
92
94
93
97
135
123
112
KMP
93
250
91
97
97
97
119
116
120
文本串长度
2
10
2
12
2
14
算法/模式串长度
10
20
2
8
12
24
2
10
14
28
2
12
Shift or
191
80
143
228
229
278
617
615
803
Horspool
227
240
136
471
598
507
2101
2108
1769
Quick search
242
268
232
790
630
666
2916
2531
1861
KMP
230
189
260
514
501
470
1718
1430
2079
当我们取模式串长度为 logN 时,图像如下: