Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
49 views

Multitape Turing Machine to accept power of 2 length 0's string?

I have been trying to find a multitape Turing Machine in order to accept a input string which consists on 0's and whose length is a power of 2: However, Im getting troubble finding it, because I dont ...
Javier's user avatar
  • 1
0 votes
0 answers
27 views

How to compute an inverse suffix array $ISA$ from a suffix array $SA$ efficiently?

I cannot help but wonder: how to compute an inverse of a suffix array, preferably in linear time? For $ISA$, it holds that $ISA[SA[i]] = i$.
coderodde's user avatar
0 votes
0 answers
19 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
0 votes
0 answers
20 views

Proof Closer String/Consensus String/Center String is NP-hard

Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
shinichi's user avatar
0 votes
0 answers
26 views

Use case for string matching in a 2 by n grid

In a 2 by n grid there is a character in each cell. A path can start at any cell and then you can move to right or down. This way each path will denote a string written by characters on cells visited ...
Iridescent 53's user avatar
2 votes
1 answer
83 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
0 votes
0 answers
13 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
70 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
  • 183
3 votes
1 answer
96 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
77 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
0 votes
0 answers
20 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
52 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
72 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
375 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
60 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
85 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
61 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
79 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
119 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
223 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
78 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
69 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
1 vote
0 answers
205 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
209 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
194 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
53 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
724 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
40 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
784 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
2 votes
3 answers
77 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
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
1 answer
70 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
72 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
  • 23
1 vote
1 answer
135 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
160 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
1k 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
80 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
70 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
191 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
33 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
122 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
54 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
37 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
55 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
246 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
492 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
  • 131

1
2 3 4 5
11