В общих словах:

строчка длины N
Общее количество подстрок N*(N+1)/2;
1) считаем Z-функцию строки, ищем её максимальное значение
2) вычитаем из общего количества подстрок максимум Z-функции
3) отрезаем от строчки первый символ и зацикливаем на пункт 1 пока строчка не пуста

Z-функция
z[i] - длинна наибольшего суффикса, начинающегося с i-го элемента и равного префиксу строки.
считается за N. ( http://www.e-maxx.ru/algo/z_function )