Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2412.00222 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910722098724864 |
|---|---|
| author | Saha, Apurba Kaowsar, Iftekhar Hakim Siyam, Mahdi Hasnat Rahman, M. Sohel |
| author_facet | Saha, Apurba Kaowsar, Iftekhar Hakim Siyam, Mahdi Hasnat Rahman, M. Sohel |
| contents | Two strings are considered to have parameterized matching when there exists a bijection of the parameterized alphabet onto itself such that it transforms one string to another. Parameterized matching has application in software duplication detection, image processing, and computational biology. We consider the problem for which a pattern $p$, a text $t$ and a mismatch tolerance limit $k$ is given and the goal is to find all positions in text $t$, for which pattern $p$, parameterized matches with $|p|$ length substrings of $t$ with at most $k$ mismatches. Our main result is an algorithm for this problem with $O(α^2 n\log n + n α^2 \sqrtα \log \left( n α\right))$ time complexity, where $n = |t|$ and $α= |Σ|$ which is improving for $k=\tildeΩ(|Σ|^{5/3})$ the algorithm by Hazay, Lewenstein and Sokol. We also present a hashing based probabilistic algorithm for this problem when $k = 1$ with $O \left( n \log n \right)$ time complexity, which we believe is algorithmically beautiful. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00222 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithms for Parameterized String Matching with Mismatches Saha, Apurba Kaowsar, Iftekhar Hakim Siyam, Mahdi Hasnat Rahman, M. Sohel Data Structures and Algorithms Two strings are considered to have parameterized matching when there exists a bijection of the parameterized alphabet onto itself such that it transforms one string to another. Parameterized matching has application in software duplication detection, image processing, and computational biology. We consider the problem for which a pattern $p$, a text $t$ and a mismatch tolerance limit $k$ is given and the goal is to find all positions in text $t$, for which pattern $p$, parameterized matches with $|p|$ length substrings of $t$ with at most $k$ mismatches. Our main result is an algorithm for this problem with $O(α^2 n\log n + n α^2 \sqrtα \log \left( n α\right))$ time complexity, where $n = |t|$ and $α= |Σ|$ which is improving for $k=\tildeΩ(|Σ|^{5/3})$ the algorithm by Hazay, Lewenstein and Sokol. We also present a hashing based probabilistic algorithm for this problem when $k = 1$ with $O \left( n \log n \right)$ time complexity, which we believe is algorithmically beautiful. |
| title | Algorithms for Parameterized String Matching with Mismatches |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.00222 |