Questions tagged [substrings]
Questions about algorithms related to substrings, or about properties of substrings.
144
questions
2
votes
1
answer
61
views
Longest Fibonacci word
We define Fibonacci words as: $F_0 = a, F_1 = b, F_{n+2} = F_n F_{n+1}$, $a, b$ can be any symbols.
How can we find the longest Fibonacci sub-word in a given string in linear time?
This question is ...
- 21
1
vote
1
answer
38
views
Problem identification: splitting string into tokens taken from a given, possible overlapping set
I am facing the following problem in a script I am trying to develop:
Given a string and a set of tokens, where the tokens are known and are overlapping (the set can contain the tokens 'a', 'b' and '...
- 111
1
vote
0
answers
40
views
Simultaneous matching of all Caesar rotations of a pattern in a text
Suppose we have an alphabet of size $S$, a pattern of length $P$ and a text of length $T$. We want to design an algorithm for matching all caesar rotations of the pattern $P$ in the text $T$. The ...
- 431
1
vote
1
answer
78
views
Minimum pumping length of a context-free language
I was studying about the minimum pumping length of the language $L$ containing all palindromes over $\{a,b\}$ from this material about the pumping Lemma for CFLs.
The productions are as follows:
$$S\...
- 113
0
votes
0
answers
14
views
What algrorithm computes a mutally exclusive partitioning from two regulair expressions?
The Question
A regular expression, such as AL+[EYI]+, represents a set of strings.
...
0
votes
0
answers
86
views
Creating a Turing machine for Substring and Equal String
How should I go about creating a single-tape Turing machine for the following language:
$$
x_{1,2} = \bigl\{ (a\#b) \mid (a,b) \in \{0,1\}^* \text{and a is a substring of b or a is equal to b} \bigl\}...
- 1
0
votes
1
answer
46
views
Shortest string which all input strings is its substring
Given a set of input strings, how do I find a shortest string S so that all input strings appear as a substring of S?
for example:
...
- 193
2
votes
1
answer
102
views
Does my finite state automaton accept a string iff it contains the given string as a substring?
I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone ...
- 125
1
vote
1
answer
56
views
Find the no of substrings a character is part of
I am looking for a O(1) solution for finding the number of substrings a character is part of.
For instance, let s = "abcde" and all substrings of s are
<...
- 113
1
vote
1
answer
71
views
Reconstructing a string from two its partitions into substrings of varying size
Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice.
Under an ...
- 161
1
vote
1
answer
26
views
number of substrings in same position with same contents
L1 and L2 are two lists which only consist of X's and Y'...
- 13
1
vote
0
answers
156
views
Is there a faster alternative to Aho-Corasick when searching for any occurrence rather than all occurrences of each of the substrings?
Aho-Corasick can result in a quadratic number of matches because it finds all occurrences of each searched-for substring. What is a faster algorithm or modification to this one to simply determine if ...
- 111
0
votes
1
answer
175
views
Longest prefix of string S that is also a sub-prefix of S in linear time
As the question suggest. I want an algorithm that runs in linear time which finds the longest prefix of a substring that is a sub-prefix of the same string.
Formally:
Given a string $S$ of length $n$,...
- 3
1
vote
0
answers
26
views
DC3/Skew Suffix Array Algorithm doesn't work for specific cases
When applying the DC3/Skew algorithm to the string yabadabado, I can't quite get it to sort correctly. This issue happens in other cases, but this is a short example to show it.
This first table is ...
- 111
2
votes
2
answers
650
views
Count number of non-contiguous occurrences in string
Given strings $S,T$ such that $n=|T|>|S|$ , I'd like an algorithm to count number of occurrences of $S$ in $T$ (as a subsequence), not necessarily contiguous.
Example:
if $T=aababc, S=abc$, the ...
- 315
3
votes
1
answer
93
views
The smallest periods of the prefixes of the Fibonacci word
I'll start with some definitions to simplify the rest of the message.
Let's denote $f_0 = b, \ f_1 = a, \ f_n = f_{n-1} \cdot f_{n-2}$, where $\cdot$ stands for concatenation of two words. We call $...
- 65
0
votes
0
answers
59
views
What algorithm will determine if two strings match eachother or not?
$\require{enclose}$
Definition of parent
For any three strings $x$, $y$, and $p$, we say that $p$ is a parent of $x$ and $y$ if and only if all of the following:
$p$ is a $\enclose{updiagonalstrike, ...
2
votes
1
answer
111
views
Efficiently find longest common substring for all substring pairs of S and T
I am trying to find the Gesalt similarity of a string $S$ and all substrings of $T$ using Gestalt Pattern Matching (Ratcliff Obershelp Algorithm)
This algorithm requires me to find the matches of S ...
- 21
1
vote
2
answers
4k
views
Maximum difference between maximum and minimum frequency in a subarray
Can anyone please help me with a better solution than O(n^3) for this problem?
So the problem is given a string, we want to output the substring's length where freqency[c1] - frequency[c2] is MAX.
c1 =...
- 53
1
vote
0
answers
120
views
Is there an efficient algorithm for finding a minimal common subset of pairwise distinct bits in a set of bit strings?
I am working on an efficient mapping function represented as a directed graph. In essence, it is a sort of radix trie. A path must be formed from a bit string [string hereon] efficiently. To do this, ...
- 97
2
votes
3
answers
310
views
Complexity of string comparison vs whitespace-trimmed string comparison
I recently worked on an algorithm which, among other things, checks strings for equality using the classic builtin equality operator:
str1 == str2
(I think it ...
- 73
1
vote
1
answer
41
views
Hints for efficient computation of the maximum length of a binary sequence
Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, ...
- 113
1
vote
2
answers
74
views
Polynomial algorithm for the «Input Series» Problem
Can you help me design an algorithm to solve the following problem in polynomial time?
Let n be a given natural number. We define an input series of length n to be a string of length n which is built ...
- 61
2
votes
1
answer
175
views
Find repeated patterns in a string via lossy compression
Description
The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
- 123
1
vote
0
answers
48
views
Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]
I'm trying to solve following problem:
Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
1
vote
0
answers
35
views
Longest substring creating palindromic substring in other string
Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$.
I ...
- 111
1
vote
1
answer
100
views
Palindrome operations on a string
You are given a string S initially and some Q queries. For each query you will have 2 integers L and R. For each query, you have to perform the following operations:
Arrange the letters from L to R ...
4
votes
0
answers
131
views
Sequence where every subset exists as some contiguous subsequence
Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
- 113
1
vote
1
answer
243
views
Counting substrings of a string that do not contain a given string
Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...
- 41
1
vote
0
answers
33
views
Has anyone seen the following string classifier discussed?
The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea.
Given a set of ...
- 111
2
votes
1
answer
486
views
Z-function and the minimum string period
Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of ...
- 41
1
vote
1
answer
82
views
Is this string substitution problem decidable?
We have the following task:
Take as input a finite set of string pairs. Each pair represents a substitution. Replace exactly one instance of the left with the right. A substitution can only be ...
2
votes
1
answer
350
views
Number of subsequence with k distinct characters
"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order."
Suppose we have string s="aabca&...
- 31
4
votes
1
answer
159
views
Is there a linear-time solution to the minimum window substring problem, provided the characters in the substring must be in order?
Suppose there are two strings, $S$ and $T$, and we want to find the length $l$ of the shortest substring of $S$ which contains all the characters in $T$, in order. (Assume the length of $T$ is bounded,...
- 143
1
vote
1
answer
63
views
Is string spliting formally defined when the string delimiter is an empty string?
Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you:
...
- 113
1
vote
1
answer
119
views
How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]
I was asked this question today:
given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n]
IF we ...
- 141
1
vote
0
answers
432
views
Boyer-Moore jump table
I have a pattern $P$ of length $m$, i.e. $P = p_0, p_1, \ldots, p_{m-1}$
which I want to build a simple jump table for (not considering special optimizing cases for now).
I only want to build a jump ...
- 145
2
votes
0
answers
76
views
Smart String search algorithm
I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible.
For example, if a query is for the ...
- 21
0
votes
0
answers
923
views
Turing Machine substring
I want to create a turing machine that describes the language L={x#y | x,y\in {0,1}* and x is a substring of y}.
However I'm not sure how to start writing the transition function δ as I've just gotten ...
- 127
1
vote
1
answer
106
views
$\omega$-string avoiding a set of substrings
Given a set of strings $S$ over $\{a,b\}$. How to determine whether there is an infinite sequence consisting of ${a, b}$ (i.e., a $\omega$-string), which doesn't have any string in $S$ as a substring?
...
- 137
5
votes
4
answers
772
views
Is there a formal definition of sub-instances or sub-problems?
A decision problem is denoted as a language $L \subseteq \Sigma^{*}$.
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some ...
- 623
0
votes
2
answers
135
views
If we want to map abbreviations of full-English words (e.g. map "Jan" to "January"), how can we identify abbreviations which map to multiple words?
Short Version:
How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")?
The set of all abbreviations is ...
2
votes
1
answer
79
views
Is there a way to determine whether a list of integers can be a prefix function?
Say you had
(0,0,0,1,2,3,4,5,6,7,8,9,10)
or
(0,1,0,1,0,1,2,3,0,1,0,0,1)
Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a ...
- 123
0
votes
0
answers
79
views
Best way to find and store difference between two strings
I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
2
votes
1
answer
58
views
Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?
Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.
I have a puzzle: ...
- 23
1
vote
1
answer
305
views
finding all cyclic substrings of a string
I have been stuck on this problem for a while now; any help would be appreciated.
Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
- 43
1
vote
1
answer
260
views
Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?
I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.
Example:
Set 1:
...
- 143
2
votes
0
answers
108
views
Shortest common cyclic superstring
The shortest common cyclic superstring problem is closely related to the shortest common superstring problem. The difference is that each of the strings in the input set may have an arbitrary rotation ...
- 364
3
votes
1
answer
617
views
Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?
Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of ...
1
vote
1
answer
24
views
What is the shortest superstring for $\{c (ab)^k, (ba)^k, (ab)^k c\}$?
In this paper on PDF page 3, they give $\{c (ab)^k, (ba)^k, (ab)^k c\}$ as an example of an input to the GREEDY algorithm for shortest superstring that causes it to have an approximation ratio of 2.
...
- 364