# Tagged Questions

The tag has no usage guidance.

130 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 ...
274 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 ...
564 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 ...
217 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 ...
170 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): ...
289 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 ...
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 ...
788 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.
120 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 ...
380 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 ...
407 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 ...
479 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 ...
185 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 ...