Exact String Matching Algorithms

		1999
Algorithms	Total	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
Brute Force	3072	123	117	137	201	181	260	344	257	379	398	359	316
Boyer & Moore	2980	151	102	148	352	220	288	228	245	287	374	340	245
Knuth, Morris & Pratt	2925	135	97	127	201	197	245	294	193	314	303	376	443
Karp & Rabin	1669	44	54	88	156	120	141	128	116	195	247	192	188
Quick Search	1267	33	45	68	83	110	131	129	113	161	147	135	112
Automaton	1247	41	42	63	102	82	90	129	85	161	157	168	127
Morris & Pratt	1123	34	46	64	87	86	91	123	88	133	131	124	116
Turbo Boyer Moore	1019	32	49	64	93	63	80	115	108	122	110	103	80
Shift Or	989	38	48	55	77	75	74	96	71	118	123	121	93
Horspool	794	28	29	53	60	49	69	87	65	96	90	88	80
Simon	736	12	29	40	59	55	62	98	67	82	76	77	79
Not So Naive	723	21	29	32	64	50	58	94	50	88	81	93	63
AlphaSkip	653	17	23	34	26	46	54	93	56	71	90	80	63
Skip	649	15	29	33	38	56	62	72	65	70	77	79	53
SMOA	609	17	31	32	40	44	47	74	61	61	74	72	56
Optimal Mismatch	603	18	27	33	42	51	48	71	53	65	65	71	59
KmpSkip	551	17	27	20	24	37	43	69	54	52	78	77	53
Colussi	519	9	19	26	42	38	35	73	39	62	59	67	50
Two Way	502	12	19	20	38	30	42	65	34	72	61	57	52
Apostolico & Crochemore	481	12	18	26	45	29	30	66	34	60	53	56	52
Smith	479	9	19	34	37	33	44	72	43	55	55	36	42
Zhu & Takaoka	469	11	22	32	31	25	39	64	40	58	61	46	40
Apostolico & Giancarlo	461	8	21	30	32	35	28	59	41	50	67	51	39
Turbo Reverse Factor	454	7	20	26	22	28	47	63	38	50	63	52	38
Raita	452	7	21	26	29	26	37	60	48	56	57	47	38
Reverse Factor	452	10	24	31	25	37	40	60	38	50	59	47	31
Galil & Giancarlo	448	8	19	29	39	27	29	64	38	48	49	51	47
Maximal Shift	448	18	21	23	24	30	35	55	35	55	56	56	40
Reverse Colussi	404	11	18	26	25	24	31	58	37	37	57	45	35
Galil & Seiferas	379	5	16	21	27	25	26	53	33	45	47	45	36
Tuned Boyer Moore	334									69	88	81	96
Total	27891	903	1081	1441	2121	1909	2306	3056	2245	3222	3453	3292	2862

page d'accueil

Thierry Lecroq