Təkrarlanan alt sətirlər

Sətirlərin təhlili, xüsusilə DNT və zülal molekullarının öyrənilməsində, biologiya və kimya sahələrində tez-tez rast gəlinən bir tətbiqdir. Bu kontekstdə maraqlı məsələlərdən biri, uzun bir sətirdə ən azı iki dəfə təkrarlanan alt sətirlərin sayını müəyyənləşdirməkdir.

Sizə verilmiş sətirdə 100 000 simvoldan çox olmayan təkrarlanan alt sətirlərin sayını tapmalısınız. Bir dəfədən çox rast gəlinən hər hansı unikal alt sətir nəzərə alınmalıdır. Məsələn, "aabaab" sətiri 5 təkrarlanan alt sətirə malikdir: "a", "aa", "aab", "ab", "b". "aaaaa" sətirində isə təkrarlanan alt sətirlər "a", "aa", "aaa", və "aaaa"dır. Qeyd edək ki, təkrarlanan alt sətirlər üst-üstə düşə bilər (ikinci nümunədəki kimi "aaaa").

Giriş məlumatları

Birinci sətir testlərin sayını (ən çox 10) ehtiva edir. Sonrakı sətirlər boş deyil və 100 000 simvoldan çox deyil.

Çıxış məlumatları

Hər test üçün müxtəlif unikal təkrarlanan alt sətirlərin sayını ayrı sətirdə çıxarın. Cavab işarəli 32-bit tam ədəd kimi yerləşdirilir.