12

The obvious way to go is dynamic programming: let $F(i,j)$ store the two letters for which a Fibonacci word of order $i$ starts at position $j$, and calculate this by looking at $F(i-2,j)$ and $F(i-1,j+\operatorname{fib}(i))$. This takes $O(n \log n)$ time at most, because there are only logarithmically many possible values of $i$. But I suspect that there ...


3

Although not specifically aimed at (rooted) trees, I think the G-trie data structure might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.


3

I think what you want is the Wagner-Fischer algorithm: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm The key insight is that, since the dictionary you are traversing through is sorted, two consecutive words are very likely to share a long prefix so you don't need to update the whole matrix for each distance calculation.


2

There is some work on developing an algebraic or grammar-based view of string algorithms, for example Robert Giegerich, Carsten Meyer, Peter Steffen: A discipline of dynamic programming over sequence data. Sci. Comput. Program. 51(3): 215-263 (2004) Robert Giegerich, Hélène Touzet: Modeling Dynamic Programming Problems over Sequences and Trees with Inverse ...


2

You are asking about "quasiperiodicity". This is a well-studied topic and a google scholar search will turn up many papers about it. For example, there is an $O(n (\log n)^2)$ algorithm here and an $O(n \log n)$ algorithm here.


1

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here: https://www.hyperscan.io/2015/10/20/match-regular-expressions Apparently, they didn't find a fast algorithm (in the worst case) ...


1

Main explicitly states that his algorithm may output some nonleftmost or nonmaximal occurrences of periodicities. Indeed, theorem 3.4 only guarantees that every leftmost maximal periodicity will be reported at least once and that total size of the output is linear in size of input string. Namely, It may report some nonmaximal periodicity, which is suffix of ...


1

In general, no, but it's difficult to prove a negative given that there might be some data structure equivalent to a BWT that provides the prediction capability. The L vector in the BWT is simply a list of the input string's characters sorted by their following context, i.e. the suffix that begins immediately after each character. Its information content ...


1

A while back I wrote up Ronald Read's tree canonization algorithm and put it on wikipedia. I would make a hashtable for each internal node signature, and label them with a list of pointers back to the subtrees they came from. However, it will only work for treelets with true leaves.


Only top voted, non community-wiki answers of a minimum length are eligible