About this document

Compressed Suffix Trie Solution by djoseph_1 is a document available to read on EtoBox.

This document provides a sample solution for string matching using a compressed suffix trie constructed from the concatenation of two strings S1 and S2 separated by delimiter symbols. It explains that the trie can be constructed in O(|S1| + |S2| + sort(Σ)) time and trimmed to focus on S1 and S2 in additional O(|S1| + |S2|) time. It then describes how to traverse the trie to count the number of substrings of S1 of length at least k that occur in S2 in O(|S1| + |S2|) time by accounting for substrings represen

Author

djoseph_1

Language

EN