Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about algorithms related to substrings, or about properties of substrings.

0
votes
0answers
3 views

String Search - how to find the “most” accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
3
votes
1answer
140 views

Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
2
votes
1answer
14 views

Approximating unique string occurrences using a small, fixed amount of memory

Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
1
vote
1answer
43 views

Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
0
votes
1answer
10 views

A hangman variation: determining a string by guessing substrings contained in it

I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I ...
4
votes
3answers
81 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
2
votes
0answers
36 views

Counting subarrays where each number either doesn't occur or occurs odd number of times

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times. ...
2
votes
1answer
92 views

Finding the maximum substring for which a given predicate is true

Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$. Assume that $F$ satisfies the following: If $F(g) = \text{true}$, then ...
2
votes
2answers
522 views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
1
vote
1answer
124 views

Longest repeated substring

I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am ...
5
votes
1answer
377 views

Find all substrings that fit the mask with asterisks

There is a problem. Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings ...
4
votes
1answer
216 views

Finding the smallest string that contains a given set of substrings

The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible....
0
votes
0answers
29 views

Suffix Trie with indexes of the last substring

As I understood there is a algorithm ("black box") that build trie from a string by O(n) time complexity, This algorithm use pointer to the first appearance of the substring in the string. Is the a ...
0
votes
2answers
369 views

Smallest length such that all substrings of that length contain at least 1 common character

Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common ...
0
votes
0answers
93 views

Computing substring language on automata

Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes). I would like to ...
3
votes
1answer
68 views

Maximum number of different substrings in big string

I'm trying to find the maximum number of different substrings of string consisting only of lowercase letters 'a' - 'z', if the length of string can be up to $5000$ Firstly, I was thinking that the ...
0
votes
1answer
78 views

Fastest way to check if prefix of small string is substring of big string

Let's say we have given 2 strings $A, B$, and let's suppose that the size of $A$ is pretty small (100 characters) and the size of $B$ is pretty big (1 million). We define prefix of string $S$ as ...
3
votes
1answer
40 views

Minimum number of nucleotides to force duplicate substring

There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T. Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of ...
1
vote
1answer
709 views

What is correct time complexity of the substring generation algo

The naive algorithm for generating all unique substrings involves traversing all the string from 1..n, thus takes $\mathcal{O}(n^2)$, but it also involves ...
7
votes
1answer
95 views

Subsequence of one string but not of others

Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet. Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of ...
1
vote
4answers
2k views

I'm looking for an algorithm to find unknown patterns in a string

I am trying to detect patterns in huge code bases. I managed to filter the entire codebase into a tagged string, as in: ABACBABAABBCBABA The result should be: ABA *3 CBA *2 I'm trying to build / use ...
3
votes
3answers
276 views

What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?

Here are some sequences: '0.66666' [3,0,1,2,2,2,0,1] 'banana' 'bandana' '11221122' I would like to find the index and length of the substring in each which is ...
4
votes
2answers
181 views

Algorithm: given very large file of strings, find lines containing substring

I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant. On the job interview I was asked a question: lets say we have a very large file, containing ...
0
votes
1answer
282 views

O(n) Palindromic Substring: Why is O(n^2) needed here?

I have been doing dynamic programming problems, and I came across a palindromic substring question. I answered it quickly, and found an $O(n)$ dynamic programming solution, but when I check the ...
0
votes
0answers
47 views

Why is step 4 and 5 necessary in this Cycle Cover Superstring Algorithm?

(Shortest Common Superstring: Input: A set S = {s1, . . . , sn} of strings over an alphabet Σ. Feasible solutions: Each superstring w of S, i.e., each string w that contains all strings $s_i$ ∈ S as ...
0
votes
1answer
105 views

Algorithm for smallest String without a given prefix

How can I find the lexicographicaly smallest string that doesn't start with a given prefix AND is lexicographicaly bigger than the given prefix? Example: prefix : cat; next string : cau prefix : ...
1
vote
0answers
286 views

most efficient way to compute number of anagrams of a string

This is a question from Hackerrank. Given a string S, find the number of "unordered anagrammatic pairs" of substrings. In other words, find the number of unordered pairs of substrings of S that are ...
3
votes
1answer
104 views

Probabilistic Substring Match

I'm looking for an algorithm that will help me determine substring matches at scale. I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage ...
1
vote
1answer
6k views

DFA - Accept all strings that does not contain a certain substring [duplicate]

So I have been trying to create a Deterministic Finite Automaton(DFA) in Jflap that accepts all strings from the alphabet {a, b, c} except those that contain the substring "abc". However i keep ...
0
votes
2answers
366 views

How to approach DFA construction with substring constraints?

We have to construct a DFA over the alphabet 0 and 1 for: Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its ...
0
votes
0answers
104 views

Algorithm to compute string prefix similarity

Given a string, how to get the its prefix similarity? I use an example to explain what I mean by string prefix similarity. Say, s = "ababaa". We take all its suffixes, that is, "ababaa", "babaa", "...
0
votes
1answer
105 views

How to extract parent, child and grandchild from a treeview fomatted string?

I have a long string that contains data formatted in the following way: var str = "parent /n /t child /n /t child /n /t /t grandchild /n parent"; If you print ...
1
vote
1answer
237 views

Check whether set of strings is prefix-free via lexicographic sort?

I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So ...
1
vote
0answers
35 views

Why is the second while loop in KMP not a conditional statement?

When building the partial match table for KMP: ...
0
votes
1answer
69 views

Search String Algorithm in Table

For a given database table: ...
0
votes
2answers
402 views

Longest substring with consecutive repetitions

I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring of $...
3
votes
2answers
700 views

Which is the proper algorithm to figure repeated substrings of longest total length?

Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$. In other words, the value of $T$ is the length ...
2
votes
2answers
83 views

Storage cost of a suffix array

MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size ...
2
votes
1answer
331 views

How is n-gram different from k-mer?

How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and ...
5
votes
1answer
106 views

String searching, where we allow characters to almost-match

Let $\Sigma= \{1,...,n\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a ...
6
votes
1answer
456 views

Finding a certain prefix of a string

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a ...
1
vote
1answer
38 views

Assign numbers to letters with respect to lowest graph peaks

I have string which is composed of letters. I want to assign each letter a unique number (letters that repeats should have assigned same number as first unique letter occurrence) and plot those ...
3
votes
0answers
73 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
4
votes
1answer
3k views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
4
votes
0answers
332 views

Number of distinct substrings

I know how to find the number of distinct substrings for a string (using suffix arrays) and I was wondering if there was a way to find this number for all of its prefixes. I already have an $O(N^2)$ ...
9
votes
1answer
729 views

Given n strings, is one of them a substring of another?

Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an ...
1
vote
1answer
1k views

Which algorithm to use to find all common substring (LCS case) with really big strings

I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other ...
5
votes
1answer
3k 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$ ...
10
votes
1answer
543 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \...
0
votes
2answers
2k 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 =...