On the Worst-case Behavior of String-searching Algorithms
Any algorithm for finding a pattern of length k in a string of length n must examine at least n-k+1 of the characters of the string in the worst case. By considering the pattern 00…0, we prove that this is the best possible result. Therefore there do not exist pattern matching algorithms whose worst...
| Autor principal: | |
|---|---|
| Publicado em: |
2023
|
| Acesso em linha: | https://hdl.handle.net/1721.1/148899 |