Trie is not important at all. With O(n) memory, precomputing the rolling hash in O(n) time, you can get a hash of a prefix/suffix (or any substring) in constan

Trie is not important at all. With O(n) memory, precomputing the rolling hash in O(n) time, you can get a hash of a prefix/suffix (or any substring) in constant time. https://cp-algorithms.com/string/string-hashing.html#calculation-of-the-hash-of-a-string https://cp-algorithms.com/string/string-hashing.html#calcula...