Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Smith waterman fallback for length > 512 #20

Open
maxRN opened this issue Feb 21, 2025 · 1 comment
Open

Smith waterman fallback for length > 512 #20

maxRN opened this issue Feb 21, 2025 · 1 comment

Comments

@maxRN
Copy link

maxRN commented Feb 21, 2025

When I try to find matches on a haystack that contains words with length > 512 (that is 513 or longer), these words get ignored in matches. I have created a reproduction test case in this PR: #19
I'm not super familiar so there is probably a better way to write the test.

Context for anyone curious (problem occurred in blink.nvim): I was using the texlab LSP for writing my thesis and in its LSP suggestions it sends the references of my bibliography along with the entire abstract. So the suggestions get very long.

@Saghen Saghen changed the title Haystacks with length > 512 get ignored Smith waterman fallback for length > 512 Feb 21, 2025
@Saghen
Copy link
Owner

Saghen commented Feb 21, 2025

We should fallback to an algorithm that doesn't scale O(nm) when n * m > threshold. We could use memchr, which we already have an implementation for, but we'd only be able to support a limited number of typos (0, 1 or maybe 2 max), which should be fine. We would also need a fallback implementation for getting matched indices but that can come later

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants