Questions tagged [substrings]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
22 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'...
picato's user avatar
  • 13
-3 votes
2 answers
46 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 ...
user168855's user avatar
1 vote
1 answer
78 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 ...
Tigerion's user avatar
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 ...
Tigerion's user avatar
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 ...
Toothpick Anemone's user avatar
2 votes
1 answer
76 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....
Ariana's user avatar
  • 123
3 votes
1 answer
95 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 ...
popcorn's user avatar
  • 183
1 vote
1 answer
69 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 '...
bracco23's user avatar
  • 111
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 ...
chubakueno's user avatar
1 vote
1 answer
83 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\...
user8718165's user avatar
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. ...
Toothpick Anemone's user avatar
0 votes
0 answers
151 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\}...
RickAbed's user avatar
0 votes
1 answer
75 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: ...
AsukaMinato's user avatar
2 votes
1 answer
138 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 ...
ZarakshR's user avatar
  • 125
1 vote
1 answer
112 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 <...
Julkar9's user avatar
  • 113
1 vote
1 answer
76 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 ...
Max Alekseyev's user avatar
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'...
20389642219's user avatar
1 vote
0 answers
197 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 ...
Display Name's user avatar
0 votes
1 answer
203 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$,...
Mikey's user avatar
  • 3
1 vote
0 answers
37 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 ...
Brother58697's user avatar
3 votes
2 answers
755 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 ...
Aishgadol's user avatar
  • 355
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 $...
dawmd's user avatar
  • 65
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, ...
Toothpick Anemone's user avatar
2 votes
1 answer
121 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 ...
Daigo's user avatar
  • 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 =...
Iris's user avatar
  • 53
1 vote
0 answers
132 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, ...
AMDG's user avatar
  • 97
2 votes
3 answers
443 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 ...
Enlico's user avatar
  • 73
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$, ...
Fabius Wiesner's user avatar
1 vote
2 answers
78 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 ...
coolest 10's user avatar
2 votes
1 answer
199 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 ...
dizcza's user avatar
  • 123
1 vote
0 answers
49 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 ...
curious.researcher's user avatar
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 ...
Nave Tseva's user avatar
1 vote
1 answer
115 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 ...
Arijeet Mohanty's user avatar
4 votes
0 answers
146 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 ...
magnetlion's user avatar
1 vote
1 answer
320 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$ ...
Conway's user avatar
  • 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 ...
Gunther Schadow's user avatar
2 votes
1 answer
567 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 ...
Conway's user avatar
  • 41
1 vote
1 answer
106 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 ...
Sriotchilism O'Zaic's user avatar
2 votes
1 answer
378 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&...
code_it's user avatar
  • 31
4 votes
1 answer
184 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,...
Brooke Chalmers's user avatar
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: ...
Tenders McChiken's user avatar
1 vote
1 answer
126 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 ...
user152503's user avatar
1 vote
0 answers
452 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 ...
PsychoKitten's user avatar
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 ...
user9041346's user avatar
0 votes
0 answers
1k 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 ...
Yuki1112's user avatar
  • 127
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? ...
Kapa's user avatar
  • 137
5 votes
4 answers
802 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 ...
Blanco's user avatar
  • 623
0 votes
2 answers
147 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 ...
Toothpick Anemone's user avatar
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 ...
MW Millar's user avatar
  • 123
0 votes
0 answers
86 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 - ...
Xenya Syrbulova's user avatar