Skip to main content

Questions tagged [strings]

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

Filter by
Sorted by
Tagged with
27 votes
2 answers
4k views

Efficient map data structure supporting approximate lookup

I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
merijn's user avatar
  • 409
43 votes
2 answers
9k views

Efficient data structures for building a fast spell checker

I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to ...
Charles Menguy's user avatar
8 votes
1 answer
6k views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
1'''s user avatar
  • 183
5 votes
1 answer
774 views

How to speed up process of finding duplicates/similar items in a large amount of strings?

Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents (...
chester89's user avatar
  • 151
21 votes
1 answer
582 views

Does every large enough string have repeats?

Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for ...
Alex ten Brink's user avatar
2 votes
2 answers
1k views

String matching for wildcard-based records

Let's say that we have a string "1.2.3" and want to find a match for it in the following records: 1.2.9 1.4.5 1.*.3 For each ...
moraes's user avatar
  • 443
2 votes
1 answer
539 views

Number of substrings possible with even characters

Consider a string 'ABBAA' Possible substrings with even number of characters are $4$ 'ABBA' : Count of 'A' is even and 'B' is even 'AA' : Count of 'A' is even and 'B' is even - ($0$) Similarly 'BB' ...
nihar's user avatar
  • 57
2 votes
1 answer
162 views

String matching

I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which ...
LoneCuriousWolf's user avatar
28 votes
1 answer
1k views

Is there a 'string stack' data structure that supports these string operations?

I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
Alex ten Brink's user avatar
17 votes
3 answers
18k views

dynamic programming exercise on cutting strings

I have been working on the following problem from this book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves ...
Mark's user avatar
  • 373
11 votes
2 answers
5k views

Fast k mismatch string matching algorithm

I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
Paresh's user avatar
  • 3,338
10 votes
4 answers
4k views

Algorithm Request: "Shortest non-existing substring over given alphabet"

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
user232362636's user avatar
8 votes
2 answers
4k views

Automaton for substring matching

Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$? I am mostly ...
Ofek Ron's user avatar
  • 355
7 votes
2 answers
739 views

How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. ...
Raphael's user avatar
  • 72.6k
7 votes
1 answer
2k views

Finding the smallest string that contains a given set of substrings

The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible....
Vel's user avatar
  • 73
6 votes
1 answer
393 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 ...
Future Security's user avatar
5 votes
2 answers
3k views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm? I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. ...
Edmon's user avatar
  • 297
4 votes
2 answers
561 views

Mathematically determine if two strings are permutations of each other

I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each ...
Miguel C's user avatar
3 votes
2 answers
2k views

Dynamic programming table for finding similar substrings is too large

Substring Diff Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}...
Alexandre's user avatar
  • 349
3 votes
1 answer
287 views

Can ropes (AVL trees) be interned?

Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time? I recently implemented a rope ...
Curtis F's user avatar
  • 1,043
2 votes
1 answer
3k views

How to find longest recurring pattern from lage string data set?

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example ...
Nuwan Indika's user avatar
1 vote
0 answers
1k views

Problem with Cormen's treatment of the Rabin-Karp algorithm

I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. ...
gpuguy's user avatar
  • 1,799
0 votes
1 answer
122 views

How many segmentations are possible for a string length N?

I have a string with length N. I would like to know how many segmentations are possible to it. Consider the example abcdc the number of N = 5 All possible ...
Karun's user avatar
  • 3
15 votes
2 answers
5k views

Why is the base used to compute hashes in Rabin–Karp always primes?

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$ where $b$ is prime (all computations ...
Saurabh Jain's user avatar
13 votes
5 answers
18k views

Word Frequency with Ordering in O(n) Complexity

During an interview for a Java developer position, I was asked the following: Write a function that takes two params: a String representing a text document and an integer providing the ...
user2712937's user avatar
11 votes
1 answer
5k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
Dan D-man's user avatar
  • 524
11 votes
3 answers
4k views

Is there an algorithm for checking if a string is a catenation of palindromes?

Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution: ...
mrk's user avatar
  • 3,708
10 votes
1 answer
6k views

Find the longest repeated pattern in a string

I'm looking for an efficient algorithm to find the longest repeated pattern in a string. For example, consider the following string of numbers: ...
user avatar
10 votes
2 answers
860 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \...
William's user avatar
  • 201
8 votes
2 answers
11k 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?
Manoharsinh Rana's user avatar
8 votes
1 answer
1k views

How do I efficiently checking if a string matches any substring in a collection

I have a collection of substrings "this" "is" "a" "antelope" I need to look at any given string and answer the question "Are any of the given substrings in this ...
Cogman's user avatar
  • 183
7 votes
3 answers
8k views

Is there a data structure for efficiently searching a string that contains a given substring?

This question arose from a practical problem: given a set of texts, find one, which contains a given string (not word). Let $S$ be a set of $n$ strings, and $l$ the length of the longest string in $S$...
Somnium's user avatar
  • 275
7 votes
0 answers
1k views

Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
Peter Krauss's user avatar
6 votes
2 answers
583 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
user76284's user avatar
  • 416
6 votes
1 answer
1k views

How to compare/cluster millions of strings?

I have around 1,000,000 of strings of variable length (from 200 to 50000) that can contain 5 characters (A, B, C, D, E). What I actually want is to cluster them together if they are similar enough. ...
Ivan's user avatar
  • 273
6 votes
1 answer
650 views

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
under_the_sea_salad's user avatar
5 votes
1 answer
733 views

Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number. ...
Mohammad Al-Turkistany's user avatar
5 votes
3 answers
301 views

Assigning a unique representation to equivalent circular queues

First, a few vague definitions: Circular queues (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle"). wikipedia Let's say that 2 ...
A. Sallai's user avatar
  • 243
5 votes
1 answer
566 views

What are the effects of the alphabet size on construct algorithms for suffix trees?

For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on ...
John Smith's user avatar
5 votes
2 answers
199 views

Word tiling, where you must use each tile exactly once

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of ...
user59343's user avatar
4 votes
4 answers
2k views

Substring in a infinite sequence of numbers

I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers. Example: 1234567891011121314151617181920 ... S = 141 Result: 18 All ...
fryme's user avatar
  • 41
4 votes
1 answer
3k views

Shortest sub-sequence of one string, that's not a sub-sequence of another string

Given two strings $x$ and $y$ over the alphabet $\{A,C,G,T\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$. Example: a shortest ...
Mike's user avatar
  • 205
4 votes
1 answer
7k views

Number of distinct substrings in a string

From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$. The answer can be obtained by $$ \...
carnifex147's user avatar
4 votes
1 answer
5k views

Semantic clustering

I have a very specific question about semantic clustering. I have a list of words/phrases. I want to run an intelligent semantic clustering algorithm on this list. Please let me know what the ...
Dibyendu's user avatar
  • 141
4 votes
1 answer
3k views

Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $[i, j]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we ...
Kyuubi's user avatar
  • 273
3 votes
1 answer
931 views

A framework to capture common variation of sequence alignments

The global alignment problem can be generalized by setting the cost of some boundary gaps to 0. Gaps at both end in both strings have 0 cost, then we get the semiglobal alignment. Gaps are at the ...
Chao Xu's user avatar
  • 3,083
3 votes
1 answer
823 views

Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of ...
securitymensch's user avatar
3 votes
2 answers
935 views

Which is the proper algorithm to figure repeated substrings of longest total length?

Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$. In other words, the value of $T$ is the length ...
Guill's user avatar
  • 131
2 votes
0 answers
76 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
user5507's user avatar
  • 2,191
2 votes
0 answers
84 views

Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
Ondra Hrubý's user avatar