Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
488
questions
3
votes
4
answers
75
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
62
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 ...
- 151
0
votes
1
answer
42
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
18
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
38
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
1
vote
1
answer
131
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$,...
- 25
3
votes
1
answer
65
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
51
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
712
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
45
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 ...
- 81
1
vote
0
answers
14
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
589
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 ...
- 306
2
votes
3
answers
72
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
77
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
45
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
0
votes
0
answers
10
views
How can we disallow alternating back-and-forth which character is matched to the gap character?
When aligning two strings, how can we disallow consecutive matches to the gap character?
Introduction
It is sometimes the case that we will want to align two pieces of English-text.
Example 1A $x = $...
- 151
1
vote
0
answers
40
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
111
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 ...
2
votes
2
answers
140
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 ...
- 279
1
vote
1
answer
364
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
53
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
59
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\...
- 279
0
votes
1
answer
146
views
Time Complexity for the given algorithm
Recently, I had to implement the following algorithm (similarly). Code in Kotlin:
...
- 101
1
vote
0
answers
24
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
83
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
41
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 ...
- 165
1
vote
1
answer
33
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
50
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
132
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
223
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
40
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
96
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
281
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 ...
- 113
1
vote
2
answers
62
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
0
votes
0
answers
9
views
Text macros(replacements) based on pre-defined rules
I'm writing a web app that requires a component that let's the user input a piece of text thats automatically formatted based on something the client calls "macros". These macros have a very ...
6
votes
1
answer
118
views
Find all n bit numbers with k ones and unique under circular shift
I am trying to traverse through all uint64_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code.
The problem ...
- 61
0
votes
0
answers
26
views
If string x is conjugate to string y, how can you prove that the reverse of x is conjugate to the reverse of y?
I am relatively new to writing proofs and I am stuck trying to prove that if $x$ ~ $y$, then $x^R$ ~ $y^R$. Any help would be appreciated!
1
vote
1
answer
61
views
Quicksort for Strings
I am currently trying to study the Quicksort algorithm. I understand how it works for integers but can anyone explain how does Quicksort algorithm work with strings?
The reason for my confusion is ...
1
vote
2
answers
161
views
Prove my algorithm that solves ABC String problem in Codeforces is correct
Here's the statements of problem A, "ABC String" in Educational Codeforces Round 105 (Rated for Div. 2)
You are given a string a, consisting of n characters, n is even.
For each i from 1 to ...
0
votes
1
answer
91
views
Empty string in an ambiguous grammar?
I'm a bit confused by the role of the empty string in this ambiguous grammar:
A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S
So what ...
- 101
1
vote
0
answers
47
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
votes
1
answer
678
views
Dynamic programming to find number of ways to divide string into primes
I am studying for final algorithms exam and saw this question:
Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
- 1
0
votes
0
answers
33
views
An idempotent grammar for text decoding?
I'd like to create a function decode(x : string) such that decode(x : string) == decode(decode(x : string)).
I believe I can ...
- 133
1
vote
0
answers
31
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
0
votes
0
answers
28
views
using TRIE for strings?
I saw the following question online:
Init - Initlize data structure in O(1).
Insert(s) - Add string s to your Data Structure in ...
- 1
13
votes
5
answers
6k
views
How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?
I understand the textbook explanation of how to use dynamic programming to find the minimum edit distance between 2 strings but how do we get to pick the 2nd string?
I don't think the entire ...
- 659
6
votes
1
answer
193
views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
- 163
-1
votes
1
answer
147
views
Proving correctness for greedy algorithm in string removal problem
Problem Statement:
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
Remove substring "ab" and gain x points.
For example, when ...
- 39