Tagged Questions
1
vote
1answer
112 views
String similarity problem
We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet.
We consider the problem of converting $x$ to $y$. Using the following operations:
...
4
votes
2answers
127 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
2answers
263 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
217 views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
8
votes
2answers
967 views
dynamic programming exercise on cutting strings
I have been working on the following problem from this book.
A certain string-processing language offers a primitive operation which splits a string into two
pieces. Since this operation ...
