# Questions tagged [substrings]

100 questions
Filter by
Sorted by
Tagged with
2k views

102 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 ...
568 views

### Algorithm: given very large file of strings, find lines containing substring

I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant. On the job interview I was asked a question: lets say we have a very large file, containing ...
138 views

### Does there exist a subset of substrings for reconstructing another string?

I am looking for a high performance algorithm to check whether I can reconstruct a given string using a given set of substrings. More details: Let's say our strings are over the alphabet $\Sigma$. ...
112 views

### Maximum number of different substrings in big string

I'm trying to find the maximum number of different substrings of string consisting only of lowercase letters 'a' - 'z', if the length of string can be up to $5000$ Firstly, I was thinking that the ...
805 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 ...
62 views

557 views

### What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?

Here are some sequences: '0.66666' [3,0,1,2,2,2,0,1] 'banana' 'bandana' '11221122' I would like to find the index and length of the substring in each which is ...
18 views

### Approximating unique string occurrences using a small, fixed amount of memory

Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
186 views

### Probabilistic Substring Match

I'm looking for an algorithm that will help me determine substring matches at scale. I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage ...