Questions tagged [substrings]
Questions about algorithms related to substrings, or about properties of substrings.
154 questions
11
votes
4
answers
2k
views
Can the Kolmogorov complexity of a substring be greater than the string?
The kolomogrov complexity of an object is the length of the shortest possible computer program (in some fixed programming language) that produces this object as output.
Can the Kolmogorov complexity ...
- 213
0
votes
0
answers
61
views
Fastest algorithm to get thortest uncommon substring for every word within a list of words
Given a list of words of length $N$ where each word is off length atmost $M$, what is the best known algorithm with respect to time complexity for computing the shortest "unique" substring ...
- 243
0
votes
0
answers
54
views
Why does the Horspool algorithm check the substring backward?
I have some doubts about the need for backward checking in the Horspool algorithm.
The shift value depends only on the last character of the current window in the text. Whether the substring ...
- 146
1
vote
0
answers
64
views
Optimal common substring elimination
The problem:
You are given a list of strings as an input. You may perform any number of "token substitution" operations. A token substitution is performed by: removing any substring, ...
- 11
1
vote
0
answers
42
views
Intersections of Sets of Strings (Alabama, Alaska, Arizona, Arkansas)
Consider the following four strings of text:
Alabama
Alaska
Arizona
Arkansas
These strings of text represent four names for four different states within the United States of America.
Suppose that we ...
2
votes
1
answer
566
views
Split a String Into the Max Number of Unique Substrings: O(n^2) solution explanation (Leetcode 1593)
I found an $O(n^2)$ accepted submission to LeetCode 1593, and I don't understand why it works.
I have included the problem statement, my understanding of what the $O(n^2)$ code does, the submitted ...
- 173
1
vote
0
answers
95
views
Sliding-window string/substring algorithm based on endpoints of substring
While there are various known algorithms to check if a string contains a substring (with the simplest but least efficient one being a brute-force sliding window, and one of the most efficient but ...
- 111
0
votes
1
answer
579
views
Constructing a DFA that accepts the set of all binary strings that contain substrings "01" or "10"
I'm having trouble designing a DFA that accepts substrings of both 01 or 10. So far, I have constructed separate DFAs that accept the substrings "01" and "10" respectively.
What I'...
- 13
-3
votes
2
answers
185
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
136
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 ...
- 11
2
votes
1
answer
143
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....
- 123
3
votes
1
answer
164
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 ...
- 183
1
vote
1
answer
174
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
89
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 ...
- 461
1
vote
1
answer
133
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