The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
1answer
177 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
78 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
266 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
979 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
702 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
357 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
389 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
399 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
181 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
305 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.