Hello,

After building suffix array and LCP array you can find |LCP| of two suffixes s and t by formula ans=min{id[s]<=k<id[t]|lcp[k]}, where id[x] is index of suffix x in suffix array. Obviously if id[s]>id[t] we should swap them. Using sparse table we can answer such queries in O(1). To solve Jarvis and LCP first build string H= S[1]+$+S[2]+#+...+S[n] (separate them by different characters). Now LCP of two strings is equal to LCP of corresponding suffixes in string H. To find how many times it occurs in all strings we can just find how many times it occurs in string H. All suffixes that have prefix equal to some string are continuous subsegment of suffix array. To find left and right bound of it we can run two binary searches to find lexicographically lowest and largest such suffix. Answer is id[highest]-id[lowest]+1.

Time complexity is O(NlogN).