Строим две trie дървета - по префиксите и по суфиксите. Преномерираме думите с dfs оrder на първото дърво, така върховете в поддърветата му имат последователни номера. Заявките се свеждат до това "Колко са числата в интервала [L,R] в поддървото на връх от второто дърво. Те може да се отговорят офлайн с фенуик за O(nlogn).