The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
0answers
78 views

Count distinct and same substrings in a range

Given a string T with n lowercase letters T[1..n]. For each substrings T[l..r], we can assign them two values, k1 and k2, which are defined as following. K1 is the number of different ...
5
votes
1answer
83 views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
0
votes
2answers
100 views

Check if an array is a substring of another array

Given two sequences $A$ and $B$, we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order. Example 1. input: $A = (4 , 6 , -5), B ...
2
votes
1answer
97 views

Can not understand idea of the KMP algorithm

I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say: The ...
5
votes
0answers
65 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
-2
votes
1answer
267 views

Suffix automaton algorithm to find occurrences of substrings

Here is an attached link to a problem, the Substring query problem that I am trying to solve. It requires the use of suffix automaton,but I could not understand what is a suffix automaton. Can ...
2
votes
1answer
111 views

Find longest common substring using a rolling hash

The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ...
0
votes
1answer
61 views

string matching vs integer matching

How different are string matching and integer matching in terms of time complexity? I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute hash code for every ...
3
votes
3answers
246 views

Algorithm Request: “Shortest non-existing substring over given alphabet”

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
0
votes
1answer
97 views

A little help with regular expressions [duplicate]

I am trying to create a regular expression that will generate the following language under the {a,b,c} alphabet: all words that do not contain the substring "bbc" I am having a really hard time ...
3
votes
2answers
44 views

Drawbacks of repeating a single pattern matching procedure for many patterns

One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern. There must be some drawbacks in this approach, given the variety ...
9
votes
1answer
513 views

Counting number of sums from contiguous subarrays of an array

We are given an array $a[1 \ldots n]$ with all $a[i]>0$. Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., ...
1
vote
1answer
1k views

Number of distinct substrings in a string

From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$. The answer can be obtained by $$ ...
3
votes
2answers
360 views

Automaton for substring matching

Given s as a string of some alphabet, what is the best known algorithm to compute a corresponding automaton that accepts any string that contains s? I am mostly intrested of the lowest time ...
8
votes
2answers
649 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
39 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
242 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
286 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
88 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 ...
3
votes
2answers
661 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 ...
7
votes
2answers
1k 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
97 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 ...