Quantum Pattern Matching in Generalised Degenerate Strings
A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in $O(mn+N)$ time (Ascone et al., WABI 2024), where $m$ is the pattern length, $n$ is the number of strings and $N$ the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.16297
curl -X POST /api/v1/records/arxiv/2603.16297/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.16297/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'