Questions tagged [substrings]
Questions about algorithms related to substrings, or about properties of substrings.
149
questions
-3
votes
2
answers
42
views
A more concise Finite Automata for 10 substring?
I am learning about finite automata and trying to create a machine that matches
{w ∈ Σ∗| w does not contain the substring 10}
I created a DFA where it either starts ...
1
vote
1
answer
73
views
A problem maybe related to pattern-matching
Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$.
Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained ...
0
votes
0
answers
20
views
The language made from the context free Language (CFL) is also a CFL? [duplicate]
Let $\Sigma$ be the set {a,b} of letters. For a language $L\subset\Sigma^{*}$ over $\Sigma$, we define $\Gamma(L)$ as follows; $\Gamma(L)=\{v\in\Sigma^{*}|\exists w\in \Sigma^{*}.(|v|=|w|\wedge vw\in ...
0
votes
0
answers
18
views
What sub-sequences do strings for the standard scientific units have in common?
As motivation, a Space Craft known as the Mars Climate Orbiter failed in the year 1999.
The failure occurred because the distinction between pound-force seconds and newton-seconds was made as an ...
2
votes
1
answer
75
views
Repeated Substring Pattern
I've been working on the following challenge on LeetCode:
Problem:
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together....
2
votes
1
answer
79
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 ...
1
vote
1
answer
63
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 '...
1
vote
0
answers
43
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 ...
1
vote
1
answer
81
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\...
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
140
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\}...
0
votes
1
answer
71
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:
...
2
votes
1
answer
135
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 ...
1
vote
1
answer
107
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
<...
1
vote
1
answer
75
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 ...
1
vote
1
answer
28
views
number of substrings in same position with same contents
L1 and L2 are two lists which only consist of X's and Y'...
1
vote
0
answers
194
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 ...
0
votes
1
answer
196
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$,...
1
vote
0
answers
34
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 ...
3
votes
2
answers
738
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 ...
3
votes
1
answer
96
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 $...
0
votes
0
answers
61
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
117
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 ...
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 =...
1
vote
0
answers
131
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, ...
2
votes
3
answers
415
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 ...
1
vote
1
answer
46
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$, ...
1
vote
2
answers
77
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 ...
2
votes
1
answer
195
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 ...
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 ...
1
vote
1
answer
113
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
145
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 ...
1
vote
1
answer
315
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$ ...
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 ...
2
votes
1
answer
549
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 ...
1
vote
1
answer
98
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
372
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&...
4
votes
1
answer
179
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,...
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:
...
1
vote
1
answer
123
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 ...
1
vote
0
answers
448
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 ...
2
votes
0
answers
79
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 ...
0
votes
0
answers
987
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 ...
1
vote
1
answer
117
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?
...
5
votes
4
answers
793
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 ...
0
votes
2
answers
144
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
89
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 ...
0
votes
0
answers
85
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
74
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: ...