Worst-case behavior of string-searching algorithms. Tuza, Z. Journal of Statistical Planning and Inference, 6(1):99–103, January, 1982.
Worst-case behavior of string-searching algorithms [link]Paper  doi  abstract   bibtex   
If some conditions hold for the string pattern, then in the worst case every string-searching algorithm has to examine all the characters of the text. These conditions hold for more than half of the patterns consisting of 0's and 1's.
@article{tuza_worst-case_1982,
	title = {Worst-case behavior of string-searching algorithms},
	volume = {6},
	issn = {0378-3758},
	url = {http://www.sciencedirect.com/science/article/pii/037837588290060X},
	doi = {10.1016/0378-3758(82)90060-X},
	abstract = {If some conditions hold for the string pattern, then in the worst case every string-searching algorithm has to examine all the characters of the text. These conditions hold for more than half of the patterns consisting of 0's and 1's.},
	number = {1},
	urldate = {2017-12-18TZ},
	journal = {Journal of Statistical Planning and Inference},
	author = {Tuza, Zsolt},
	month = jan,
	year = {1982},
	keywords = {String-searching, Worst-case behavior},
	pages = {99--103}
}

Downloads: 0