Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
502
questions
0
votes
0
answers
12
views
Flowgarithm for common child program for a beginner (without pointers)
I'm a first year BCA student. Can you help me with flowgarithm of the common child problem (LCS) without pointers
0
votes
1
answer
35
views
Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.
We want $O(S)$ time complexity in an average case.
I think the solution lies in sophisticated ...
- 31
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 ...
- 31
1
vote
1
answer
40
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
0
votes
0
answers
14
views
KMP search: Can a shift by partial match prefix by non-suffix match lead to exact match?
Consider the following step where 'abaab', upon failed mismatch, 'ab' the prefix is followed by aligning at 'ab' the suffix. What confuses me is the reason for being able to discard the possibility of ...
- 101
0
votes
0
answers
41
views
finding the length of the GCD of two strings
Let's say you have two strings: a and b with GCD c. Why is it that ...
- 171
1
vote
1
answer
47
views
Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.
We are given as input:
A set of strings S of size ...
- 411
-1
votes
1
answer
121
views
Design an algorithm to predict words based on a skeleton from a given dictionary
I'm working on an algorithm which is permitted to use a training set of approximately 250,000 dictionary words.
I have built and providing here with a basic, working algorithm. This algorithm will ...
- 99
-2
votes
1
answer
54
views
Data Structure for strings on integers
Designing a datastructure which supports the following operations on integers (It can also be visualized as a datastructure on strings, if the alphabets/characters have total ordering)
Operations on ...
- 118
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.
...
2
votes
1
answer
52
views
How Can the Bounded Search Tree Algorithm for Closest String run in $\mathcal{O}(kd)$ per node?
I am trying to understand an algorithm for solving Closest String using bounded search trees, as found in Parameterized Algorithms (Cygan et al., 2015).
Assume we have a set of $k$ strings $x_1, ..., ...
0
votes
1
answer
49
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
0
answers
18
views
Optimizing the number of XML-like tags where only the innermost tag is respected
Given a string of characters (say a, b, ...) I want to wrap those characters by tags ...
- 21
1
vote
1
answer
59
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
3
votes
4
answers
119
views
Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?
The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and ...
- 267
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
0
votes
1
answer
57
views
ASCII invariant string for base64 Encoding
I know the basics about base64 encoding, but thinking about it abstractly I have a theoretical question.
If we consider base64 a mathematical function(in our case computable), Does there exists an ...
- 153
0
votes
0
answers
40
views
Performing fuzzy search queries on a large database of strings
I have a large database of strings (~10 million)
I need to perform fuzzy search queries which would find the best match inside that database.
The best match meaning the one that has the highest 'score'...
- 113
1
vote
0
answers
162
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
179
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
3
votes
1
answer
126
views
A Markov algorithm that does unary multiplication
I am learning Markov algorithms and came across the paper Markov Algorithm by CHEN Yuanmi. I am trying to understand the following example (well, any of the examples in the paper).
Example 3: ...
- 155
-1
votes
1
answer
52
views
Correct way to encode strings
I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples.
E.g. for a long string "abbccba.." with an alphabet <...
- 111
2
votes
1
answer
722
views
Can we prove that any set of finite strings without substrings is finite?
I want to prove (or disprove) the following conjecture:
Let $\Sigma$ be a finite alphabet, and let $L \subseteq \Sigma^*$
satisfy that there are no $v, w \in L$ such that $v$ is a proper
substring of ...
- 23
0
votes
0
answers
51
views
what are all the ways of delimiting blocks
To my knowledge, in block-structured programming languages, there are 2, maybe 3 main ways of delimiting a block.
Using start and end tokens, this can be brackets or reserved words etc
Using ...
- 91
1
vote
0
answers
27
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
654
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
2
votes
3
answers
74
views
Best Data Structure For Text Processing
Given a sentence like this, and i have the data structure (dictionary of lists):
{'cat': ['feline', 'kitten']}
A feline was recently spotted in the ...
- 121
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
1
answer
67
views
Number of bit string interpretations correct?
Suppose you are given a bit string $B[1 ... n]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-...
- 52
1
vote
0
answers
54
views
Understanding how the total # of comparisons is derived for the worst case in the "Brute-Force String Matching" algorithm
The Total number of comparisons for the worst case in the "Brute-Force String Matching" algorithm is: (n-m+1) where ...
- 13
1
vote
1
answer
123
views
Failure function of the Fibonacci strings (The Dragon Book Exercise 3.4.9d)
Exercise 3.4.9 of The Dragon Book defines Fibonacci strings as follows:
$s_1 = b$.
$s_2 = a$.
$s_k = s_{k-1}s_{k-2}$ for $k>2$.
Part (d) then poses the following question:
Show that the failure ...
- 13
2
votes
2
answers
152
views
How can we show that P is not closed under taking all long prefixes?
Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language ...
- 289
1
vote
1
answer
740
views
time complexity to convert string to integer and vice a versa
just given solution on this post
i had mention the time complexity to convert string to int is O(n), also verifying this post
now in one of comment fellow SO user, corrected me with example also ...
- 111
0
votes
2
answers
67
views
Is solving Binary String Matching equivalent to Solving All type of string matching?
This might be an irritating, naive question, but please bear with me. If an algorithm/code solves the string matching problem for a binary string, does not it imply that the algo/code actually solves ...
- 291
1
vote
2
answers
66
views
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.
I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\...
- 289
0
votes
1
answer
171
views
Time Complexity for the given algorithm
Recently, I had to implement the following algorithm (similarly). Code in Kotlin:
...
- 101
1
vote
0
answers
26
views
What are practical applications for markovs algorithm(string rewriting systems)
:)
Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
- 11
0
votes
1
answer
108
views
Given a list of strings enumerated over a finite alphabet, what's the most efficient way to get a string by its index?
Say you have the finite alphabet $\{a,b,c,d,e,f,g\}$ and an enumeration of finite strings over it by the shortlex order (length-lexicographic ordering), starting with the empty string, i.e.,
$\epsilon,...
- 1
1
vote
1
answer
53
views
Determine if string can be constructed from given building blocks
Let's say building blocks are X, Y, XX, YY, XY and YX. Each building block has an associated count ($c_X, c_Y, c_{XX}, \ldots$, $c_i$ can be 0).
Given a string $s$ and building block counts, figure ...
- 175
1
vote
1
answer
36
views
Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B
I've been given the question in the title:
Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in ...
- 11
2
votes
2
answers
54
views
Delete consecutive characters and add zeros at the end with a restriction
Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,
The restrictions:
$...
- 21
0
votes
1
answer
202
views
Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?
Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity?
I wrote a Python function that sorts the characters in a given string ...
- 1
1
vote
1
answer
357
views
Hash / Compression algorithm to shorten text?
I desperately need a hash / compression function that is suited to shorten text.
The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
- 31
2
votes
1
answer
52
views
Check if a string can be obtained by a sequences of insertion of "abc"
Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a_{left}+$"$abc$"$+a_{right}$, where $a=a_{left}+a_{right}$ in a prior state. $a_{left}...
user137116
1
vote
4
answers
1k
views
What is the name of the following binary encoding?
S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...]
I want to encode / decode natural numbers with the following scheme:
Encoding N: For ...
- 299
6
votes
1
answer
103
views
What properties must a string satisfy to be a possible output of the Burrows-Wheeler transform?
The Buttows-Wheeler transform is a function that takes a string $S$ to a new string $S'$ and an index $I$. The new string $S'$ is always an anagram (rearrangement) of the input string $S$.
However, if ...
- 181
1
vote
0
answers
26
views
What is the name of the following problem on sets of strings
Given finite sets $A,B,C$ of finite strings, does there exist some $x,y \in A$ and some $z$ such that $x.z \in B$ and $y.z \in C$ hold (where $x.z$ denotes the concatenation of $x$ and $z$)?
That is, ...
0
votes
2
answers
467
views
Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?
My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the ...
- 325