Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
Computer Science

Questions tagged [strings]

Ask Question

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

365 questions
Newest
Active
Bountied
1
Unanswered
Filter by
Sorted by
Tagged with
3
votes
1answer
41 views

Evaluating predicate on binary strings

Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}...
3
votes
1answer
37 views

How many “compressible” strings are there?

Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this. It is easy to see that almost all ...
0
votes
0answers
19 views

Little Endian and Decimal numbers

I understand that, for some hex string like 0xF0B0D0, the reverse byte order is 0xD0B0F0 since two hexademical digits represent ...
2
votes
1answer
81 views

Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with. I have a set of strings, for example: ...
3
votes
2answers
59 views

Why is the lower bound for sorting strings Ω(d + nlogn)?

I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})...
-1
votes
0answers
26 views

Reccomend a textbook which would be useful for developing a spell-checker or static search engine

Suppose that you are working on a search engine for a grocery store self-check-out-machine. If the end-user (human) types the string “green onions” into the check-out-machine, then green onions ...
1
vote
0answers
89 views

Finding bounded lexicographically largest string of digits but not larger than other with counted substitutions

The problem comes from the book текстовые и жадные алгоритмы (String and greedy algorithms) by a fairly unknown Russian computer scientist Николай Сухоруков. We are given two numbers $A$ and $B$ of ...
2
votes
0answers
22 views

String to small integer mapping without collision

Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts? Strings are quite often of the form of prefix + ...
0
votes
1answer
42 views

How do you define and parse variables (free or bound) from user-entered strings?

I'm writing an application in which the user might enter expressions such as $\text{lim}_{i \in I} \beta(i)$ where $\beta$ is a functor. That's just an example, the expressions, which contain ...
5
votes
1answer
206 views

Sampling a uniform distribution of fixed size strings containing no forbidden substrings

Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word? For short output strings ...
2
votes
1answer
72 views

Does this shuffle have non-zero probability for all permutations?

I was trying to do some code golf, when I created the following algorithm to shuffle a string: ...
0
votes
2answers
57 views

Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...
1
vote
0answers
16 views

Algorithm for searching string with wildcards

I'm trying to find efficient algorithm for checking if string with wildcards contains given substring. The parts of the string are separated with a "." character. So for example I have ...
0
votes
0answers
41 views

Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?

In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g. ...
0
votes
0answers
11 views

String filtering - process hundreds to millions of filters

What would be the most efficient way (whether with algorithims, cpu(s), DBs & SQL, distributed computing, etc) to process many strings, say ~1000/minute, and filter each string over 100s to ...
0
votes
0answers
37 views

Finding an substring in an infinite sequence

I'm trying to find a substring in an infinite sequence of numbers (Similar to Substring in a infinite sequence of numbers) and am a little stuck on improving my algorithm. I know there is already an ...
0
votes
1answer
34 views

Is there an algorithm to share parts of strings? [duplicate]

Let's say that we have the strings Hello, World, Hello and World. The algorithm I am ...
2
votes
2answers
89 views

Sliding Window Dictionary String Matching

Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every ...
0
votes
0answers
8 views

Count compound words with an ambiguous decomposition

I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many ...
0
votes
1answer
55 views

How to count all integers less than a given integer and having two contigous digits as $y$?

Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
0
votes
0answers
12 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
2
votes
0answers
43 views

Edit distance between all word pairs

Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs. Since there are M² word pairs, and the pairwise edit distance ...
2
votes
1answer
177 views

Sorting an array of strings by length in linear complexity

I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using ...
2
votes
0answers
23 views

Permutation to maximise strings' common prefix

Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix. Given a set $S=\{(s,w)\}$ of pairs of ...
0
votes
0answers
36 views

Suffix-automaton Largest common substring of multiple strings

Can anyone help with understanding how to solve "Largest common substring of multiple strings" problem with usage of Suffix-automaton? I've found this a really good article about SA . But ...
3
votes
3answers
229 views

CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this: S→A|B A→aE|aA|EA B→bE|bB|EB E→aEbE|bEaE|Λ ...
1
vote
1answer
173 views

Suffix array and counting distinct substrings of specific length

I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length. I started with the algorithm for counting ALL distinct substrings. I solved it after ...
2
votes
1answer
38 views

Properties of reciprocal Quines

I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same ...
3
votes
2answers
788 views

Divide two strings to form palindrome

Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome. I've ...
3
votes
1answer
234 views

Reductions between LIS and LCS

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
0
votes
1answer
48 views

Non consant size alphabet

Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.
5
votes
0answers
51 views

Number of strings at given edit distance

I would like to know the number of strings at edit distance $n$ of a string $s$. I guess this is textbook knowledge... but I cannot find the textbook in question. More formally, I have an alphabet $\...
1
vote
0answers
31 views

Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply ...
7
votes
2answers
2k views

Longest common substring in linear time

We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity. Can a solution be found in only linear time?
0
votes
0answers
288 views

Brute Force Approach for LCS and its Time Complexity

I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
2
votes
2answers
65 views

O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?

Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem. If s = little string and S = len(s) b = big string and ...
3
votes
1answer
58 views

Find the smallest set of strings which “covers” a given set of strings (coverage = containing as substring)

Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds: $\forall t \in T(k,l): k \leq |t| \leq l$ $\...
2
votes
2answers
280 views

What is an efficient data structure for prefix matching?

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
1
vote
1answer
51 views

Let u and v be two strings. What about the reverse order of their concatenaited string?

let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$? Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
0
votes
0answers
62 views

Returning all the combinations of a string using regex

Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches? For example, if the string is ...
4
votes
0answers
41 views

Highest covering repeated string

Let's say I have the following string: XXXXXAYYYYBYYYYCXXXXXDYYYY We can see that the substring XXXXX is 5 characters long, ...
3
votes
1answer
88 views

Replace queries on string

Let's define a replace query on some string $s$. Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\}, l \...
1
vote
0answers
172 views

Algorithm for DFA accepting any string with ending with a particular substring

Is there any possible general algorithm for constructing a DFA such that it accepts any string, which has a given sub-string in the suffix(end) for any given language. The algorithm should directly ...
-1
votes
1answer
221 views

Find the Most Frequent Ordered Word Pair In a Document

This is a problem from Skiena's excellent book The Algorithm Design Manual: Give an algorithm for finding an ordered word pair(e.g."New York") occurring with the greatest frequency in a given ...
0
votes
1answer
523 views

Large-scale string clustering

I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...
1
vote
1answer
48 views

Grammar of words with exactly $k$ prefixes in another grammar

Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that $$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$ where $\text{Pref}(w)$ is the set ...
0
votes
0answers
44 views

use sparse table to optimising queries in suffix array

I want to build a suffix array and handle these queries: 1.word search in a text 2.longest common prefix of two suffixes(LCP) so after making the suffix array,I want to do these requests by ...
2
votes
2answers
128 views

Why does little endian apply to numbers and not to text strings?

The Portable Executable file format is the format that Windows EXE files use. It is a binary format. Numbers are in little endian form. Thus, the following hex represents the decimal number 256, not ...
0
votes
0answers
295 views

Shortest Uncommon Subsequence

Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings? For example, Input : S = “babab” T = “babba” Output : 3The subsequence “aab” of ...
1
vote
1answer
348 views

Word ladder problem for words with different length

Is there some one who know any algorithm for word ladder problem with words of different length? Actually we have some strings with same length and some strings with one length longer but not from ...

1 2 3 4 5 … 8