The substrings tag has no wiki summary.
7
votes
2answers
141 views
An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?
This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better.
I'm ...
2
votes
1answer
34 views
terminology for grouping words in a string?
We commonly create sub-groups of strings in one particular algorithm implementation. I just want to know in CS literature is there any standard name for such kind of grouping. For e.g.
...
0
votes
2answers
123 views
Find all increasing/decreasing sub array
I have a question that I still struggle with.
It would be really appreciated if you guys could give me some hints.
Here is the problem :
Assume that $a[1\dots n]$ is an array of $n$ positive real ...
4
votes
2answers
134 views
Fuzzy string matching algorithm with allowed events?
I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions ...
2
votes
1answer
68 views
Rechecking contiguous characters (as in run length encoding)
So I have a fun little problem. It will take a minute to explain, but the situation is conceptually very simple. Suppose you have a string of characters, which is interpreted as groups of one or more ...
2
votes
2answers
269 views
Dynamic programming table for finding similar substrings is too large
Substring Diff
Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of
mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots ...
4
votes
2answers
308 views
Fast k mismatch string matching algorithm
I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
2
votes
1answer
68 views
Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?
Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w ...
