Worst-case behavior of string-searching algorithms

Worst-case behavior of string-searching algorithms. Tuza, Z. Journal of Statistical Planning and Inference, 6(1):99–103, January, 1982.

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

{"_id":"SqgJLycaijwz8kwH3","bibbaseid":"tuza-worstcasebehaviorofstringsearchingalgorithms-1982","downloads":0,"creationDate":"2018-08-26T16:08:16.487Z","title":"Worst-case behavior of string-searching algorithms","author_short":["Tuza, Z."],"year":1982,"bibtype":"article","biburl":"https://api.zotero.org/users/4543350/collections/8WTCDAGM/items?key=fF5y8imNS4C1ujxzFy92dlmr&format=bibtex&limit=100","bibdata":{"bibtype":"article","type":"article","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":[{"propositions":[],"lastnames":["Tuza"],"firstnames":["Zsolt"],"suffixes":[]}],"month":"January","year":"1982","keywords":"String-searching, Worst-case behavior","pages":"99–103","bibtex":"@article{tuza_worst-case_1982,\n\ttitle = {Worst-case behavior of string-searching algorithms},\n\tvolume = {6},\n\tissn = {0378-3758},\n\turl = {http://www.sciencedirect.com/science/article/pii/037837588290060X},\n\tdoi = {10.1016/0378-3758(82)90060-X},\n\tabstract = {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.},\n\tnumber = {1},\n\turldate = {2017-12-18TZ},\n\tjournal = {Journal of Statistical Planning and Inference},\n\tauthor = {Tuza, Zsolt},\n\tmonth = jan,\n\tyear = {1982},\n\tkeywords = {String-searching, Worst-case behavior},\n\tpages = {99--103}\n}\n\n","author_short":["Tuza, Z."],"key":"tuza_worst-case_1982","id":"tuza_worst-case_1982","bibbaseid":"tuza-worstcasebehaviorofstringsearchingalgorithms-1982","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/037837588290060X"},"keyword":["String-searching","Worst-case behavior"],"downloads":0},"search_terms":["worst","case","behavior","string","searching","algorithms","tuza"],"keywords":["string-searching","worst-case behavior"],"authorIDs":[],"dataSources":["WGuzu8d9YYFsR6WY7"]}