LeetCode 3045. Count Prefix and Suffix Pairs II

Using trie tree and z-algorithm to find prefix and suffix.