Questions tagged [strings]

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

55 questions
Filter by
Sorted by
Tagged with
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 ...
8k 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 ...
4k 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 ...
429 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 (...
509 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 ...
177 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' ...
121 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 ...
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 ...
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 ...
16k 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 ...
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 ...
3k 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 ...
662 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. ...
1k 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....
526 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 ...
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 ...
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 ...
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. ...
207 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 ...
2k views