1 / 2 Suffix Arrays, Automata & Aho-Corasick

Fifteen Distinct Substrings

The suffixes of s = "banana" in sorted order:

rank start index suffix
0 5 a
1 3 ana
2 1 anana
3 0 banana
4 4 na
5 2 nana

lcp[i] is the longest common prefix of the suffixes at ranks i and i+1. The count of distinct substrings is

n(n+1)2−∑ilcp[i]\frac{n(n+1)}{2} - \sum_i \text{lcp}[i]

Which pair is right?

A

lcp = [3, 1, 0, 2, 0], 15 distinct substrings

B

lcp = [1, 3, 0, 0, 2], 15 distinct substrings

C

lcp = [1, 3, 0, 0, 2], 21 distinct substrings

D

lcp = [0, 1, 3, 0, 0, 2], 15 distinct substrings