# Tag Info

14

Let $m$ and $n$ be the lengths of two given strings, Linear time assuming the size of the alphabet is constant. Yes, the longest common substring of two given strings can be found in $O(m+n)$ time, assuming the size of the alphabet is constant. Here is an excerpt from Wikipedia article on longest common substring problem. The longest common substrings of a ...

4

Yes. There's even a Wikipedia article about it! https://en.wikipedia.org/wiki/Longest_common_substring_problem In particular, as Wikipedia explains, there is a linear-time algorithm, using suffix trees (or suffix arrays). Searching on "longest common substring" turns up that Wikipedia article as the first hit (for me). In the future, please research ...

2

This problem is well-studied; it's aptly called longest repeated substring problem. It can be solved in linear time by creating a suffix tree with Ukkonen's algorithm; the longest repeat corresponds to the labelling of the longest path from the root to an inner node which you find using breadth-first search. This does not exclude overlapping substrings. ...

2

I wrote some code in Python to solve this problem. Python is designed to be very readable. There is a plaintext explanation of the algorithm below to help you understand what's going on. I am treating the database as an array indexable by its columns and rows. def find_match(db, input_string): if input_string == '': return list() matches = ...

2

In order to implement step 2, use a hash table. Add all the hashes of the $k$-length substrings of $s$ to the table. For each $k$-length substring of $t$, look it up on the table. This takes expected linear time for a large enough hash table.

1

The theorem is used to construct a recurrence relation for computing the LCS of $X$ and $Y$. The first point states that if $x_m = y_n$, then one possible LCS of $X$ and $Y$ is an LCS of $X_{m-1}$ and $Y_{n-1}$ together with $x_m$. This is one of the cases in the recurrence relation. You ask why we are not considering $Z$ as the LCS of $X$ and $Y$. There is ...

1

Denote the two strings by $s = s_1,\ldots, s_n$ and $t = t_1,\ldots, t_m$. Let $\mathcal{U}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$ which contain $s_i$ and $t_j$. Let $\mathcal{U}(\leq i,j)$ be the union of $\mathcal{U}(I,j)$ over all $i \leq I$, and define $\mathcal{U}(i,\leq j),\mathcal{U}(\leq i, \leq j)$ ...

1

Look at row=1 and column=8 (using 0 indexed numbers) in your matrix. That value says that the length of LCS between SHINCHAN and N is 2, which is impossible since N itself is of size 1. When s1[i] and s2[j] are equal you need to look at the number in matrix[i-1][j-1] and add one and not matrix[i][j-1] (which I think you are doing). You can compare your ...

1

Extending the well-known dynamic programming algorithm for Longest Common Subsesequence, we have a poly-time algorithm for Longest Zig-zag Subsequence. When DPing, just also add another parameter: $\mathrm{A}[\mathrm{i}][\mathrm{j}]$ is the length of the longest zig-zag sequence ending at position $i$ and it is increasing when it ends at $i$ if $j = 0$ and ...

1

Swapping two non-overlapping subsequences is same as swapping two non-overlapping substrings of one of the input strings. A simple algorithm would be to guess the start and end points of the substrings that we want to swap, let them be (s1,t1) and (s2,t2), and run LCS using this swapped string. There are O(m^2*n^2) such guesses and each one takes O(m*n).

1

Consider the following two strings: $$s_1 = (abc)^n, s_2 = (bac)^n.$$ You can show that the longest common substrings of $s_1,s_2$ have length $2n$. There are at least $2^n$ of these: $\sigma_1 c \sigma_2 c \ldots \sigma_n c$, where $\sigma_i \in \{a,b\}$.

1

Rabin-Karp Rabin-Karp string search would be a good candidate, because it can use a rolling hash function. You pick a segment length $\ell$. For each "needle", you hash its first $\ell$ characters, and store it in a hashtable keyed on the hash. Then, as each character of text arrives, you compute the rolling hash of the last $\ell$ characters, look it up ...

1

From what I understand you are looking for maximal substrings of the form $y^k$ for $k\ge 2$. By some this is called a repetition in a string. One of the first to give an algorithm for finding these is Maxime Crochemore: An optimal algorithm for computing all the repetitions in a word, Inform. Process. Lett. 12 (1981) 244-248. From what I understand his ...

1

I came across this problem before. I compressed the strings and applied dynamic programming on the compressed strings. For compression techniques, I followed the methods described in this paper: http://pdf.aminer.org/000/145/966/data_compression_using_long_common_strings.pdf The speed was decent. But, it consumed some space though.

Only top voted, non community-wiki answers of a minimum length are eligible