Questions tagged [strings]

Questions about sequences of symbols, sets thereof and their properties as well as uses.

Filter by
Sorted by
Tagged with
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
Anandhakrishnan's user avatar
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 ...
popcorn's user avatar
  • 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 ...
popcorn's user avatar
  • 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 '...
bracco23's user avatar
  • 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 ...
chubakueno's user avatar
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 ...
Quiescent's user avatar
  • 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 ...
user129393192's user avatar
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 ...
Mathguy's user avatar
  • 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 ...
driver's user avatar
  • 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 ...
Vk1's user avatar
  • 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\...
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
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, ..., ...
LemongrabThree's user avatar
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: ...
AsukaMinato's user avatar
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 ...
キャラメル's user avatar
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 <...
Julkar9's user avatar
  • 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 ...
Jeremy Friesner's user avatar
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 ...
Max Alekseyev's user avatar
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 ...
Jayendra Parmar's user avatar
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'...
cubiii's user avatar
  • 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 ...
Display Name's user avatar
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$,...
Mikey's user avatar
  • 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: ...
BurnsBA's user avatar
  • 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 <...
lesobrod's user avatar
  • 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 ...
anamundi's user avatar
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 ...
StackMachine's user avatar
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 ...
Brother58697's user avatar
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 ...
Aishgadol's user avatar
  • 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 ...
Hi There's user avatar
  • 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 $...
dawmd's user avatar
  • 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-...
coderodde's user avatar
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 ...
ZenPyro's user avatar
  • 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 ...
akiarie's user avatar
  • 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 ...
Fred Jefferson's user avatar
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 ...
sahasrara62's user avatar
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 ...
Michael's user avatar
  • 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\...
Fred Jefferson's user avatar
0 votes
1 answer
171 views

Time Complexity for the given algorithm

Recently, I had to implement the following algorithm (similarly). Code in Kotlin: ...
kaneda's user avatar
  • 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 ...
Matplayerino's user avatar
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,...
Quavo's user avatar
  • 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 ...
Looft's user avatar
  • 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 ...
user3917631's user avatar
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: $...
chucha's user avatar
  • 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 ...
Daniel's user avatar
  • 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 ...
PandaPhi's user avatar
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}...
user avatar
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 ...
Oleg Dats's user avatar
  • 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 ...
Timwi's user avatar
  • 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, ...
Robert Sachtleben's user avatar
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 ...
Hang Chen's user avatar
  • 325

1
2 3 4 5
11