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#calcula...