2026-08-05T07:22:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23102 2025-10-02T12:37:33Z ddc:004 open_access

Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms Nicaud, Cyril Pivoteau, Carine Vialette, Stéphane Pattern matching branch prediction transducers average case complexity Markov chains We investigate the classical Morris-Pratt and Knuth-Morris-Pratt pattern matching algorithms from the perspective of computer architecture, focusing on the effects of incorporating a simple branch prediction mechanism into the computational model. Assuming a fixed pattern and a random text, we derive precise estimates for the number of branch mispredictions incurred by these algorithms when using local predictors. Our analysis relies on tools from automata theory and Markov chains, offering a theoretical framework that can be extended to other text processing algorithms and more sophisticated branch prediction strategies. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cyril Nicaud and Carine Pivoteau and Stéphane Vialette 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.8 urn:nbn:de:0030-drops-231027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode