Pattern Matching under Polynomial Transformation

DOI10.1137/110853327zbMath1271.68248arXiv1109.1494OpenAlexW2076643326MaRDI QIDQ2840986

Markus Jalsenius, Peter Clifford, Raphaël Clifford, Benjamin Sach, Benny Porat, Noa Lewenstein, Ely Porat, Ayelet Butman

Publication date: 24 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.1494

zbMATH Keywords

normalizationpattern matchingstring algorithms3SUM-hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (3)

A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Improved subquadratic 3SUM ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

This page was built for publication: Pattern Matching under Polynomial Transformation