The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
0answers
37 views

Finding string containing given collection of non-contiguous substrings and their multiplicity

Fix a finite alphabet. Given a collection $C=\{(s_1,m_1),\ldots,(s_k,m_k)\}$ of tuples of strings and integers. Is there an efficient algorithm to find all strings $s$ of a given length $L$ such that ...
4
votes
0answers
104 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

I already posted this question here but I didn't receive an answer, so I'm posting it here as well :) Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as ...
-2
votes
1answer
86 views

What is the applications of kmp algorithm? [closed]

KMP algorithm works best when there is/are self matching(s) of pattern string that we want to search for. Usually it doesn't happen unless pattern is long enough. So where is the KMP application in ...
11
votes
1answer
400 views

Fibonacci words

I came across the following problem in my old Czech algorithm textbook, sadly came with no hints or solution. "We define Fibonacci words as $F_{0}=a$, $F_{1}=b$, $F_{n+2}=F_{n}F_{n+1}$, where $a$ and ...
-1
votes
1answer
193 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
0
votes
0answers
104 views

Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
3
votes
3answers
278 views

Search a string for a list of words

I have a large number of long strings, and I need to search them for a given list of words as fast as reasonably possible. (Neither the strings nor the words are constants) I learned that I can ...
28
votes
2answers
1k views

Commonest Subsequence

A string has $2^n$ subsequences, but they are usually not all distinct. What is the complexity of finding the maximum frequency of any subsequence? For example, the string "subsequence" contains 7 ...
0
votes
1answer
753 views

Algorithm: Find the first k longest substrings between two similar strings

Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.
-4
votes
3answers
119 views

Text Analyze and Processing

What algorithms do you know regarding text analyze/processing? Detailed, I need to "find out" the most used words, sentences, words' combinations, their category etc (these are just examples, moreover ...
9
votes
2answers
366 views

Efficient algorithms for searching a collection of trees

I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset. Are there ...
6
votes
1answer
398 views

Number of strings with unique substrings

I have a question about binary strings with a certain property: Given an integer $n$-bit integer $p$, that is not a perfect power of $2$. Count the number of $(p+n-2)$-bit strings that have the ...
8
votes
1answer
432 views

Deciding if a wildcard string is completely matched by another wildcard string in a set

Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the ...
1
vote
0answers
183 views

Natural Language Processing. Where to start? [closed]

Natural Language Processing is an area which interests me. I know little about it and I'm hoping somebody can suggest a starting point. Basically I'd like to develop a search algorithm specific for ...
16
votes
6answers
2k views

Computing the Levenshtein distance quickly

Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance. The naive approach is, ...
4
votes
1answer
334 views

Best resources for string searching or pattern matching exercises

I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.