Problem I
Samþjappanleg lykilorð

Algengur þjöppunarhugbúnaður.

Yfirmaður þinn var að fá frábæra hugmynd fyrir nýja tegund af lykilorðum. Þar sem hlutstrengir í stærri streng eru mjög þjappanlegir, væri ekki einfaldara ef öll lykilorð væru bara hlutstrengir í einhverjum mjög stórum streng sem yrði geymdur miðlægt? Þá væri hægt að tákna öll lykilorð með einni tölu. Enginn tími til að ræða, þetta er svo frábær hugmynd að það þarf að útfæra hana strax.

Þar sem aðeins má geyma eina tölu fyrir hvert lykilorð samkvæmt yfirmanni þínum þá verða allir þessir hlutstrengir að hafa sömu lengd $K$. Segjum sem svo að stóri strengurinn sé ABBCD. Þá ef $K = 1$ eru lykilorðin sem eru í boði A, B, B, C og D. Þetta gengur náttúrulega ekki þar sem það eru endurtekin lykilorð. En ef $K = 2$ eru lykilorðin AB, BB, BC, CD í boði sem gengur upp. Eftir því sem $K$ verður stærra eru færri lykilorð í boði, svo við viljum eins lítið $K$ og mögulegt er.

Hvað er minnsta $K$ sem lætur þetta allt ganga upp fyrir gefinn streng? Það er að segja minnsta $K$ þannig að allir hlutstrengir af lengd $K$ séu ólíkir.

Inntak

Fyrsta og eina línan inniheldur einn streng. Sá strengur inniheldur aðeins prentanlega ASCII stafi og enga bilstafi. Hann hefur lengd að minnsta kosti $1$ og í mesta lagi $10^5$.

Úttak

Prentið minnsta $K$ sem lætur lykilorðaplan yfirmanns þíns ganga upp.

Útskýring á sýnidæmum

Í fyrsta sýnidæmi dugar ekki að taka alla hlutstrengi af lengd $1$ því þá fáum við hlutstrenginn B tvisvar. En um leið og við tökum lengd $2$ dugar það, því við fáum hlutstrengina AB, BB, BC og CD.

Ef við tökum lengd $1$ í seinna sýnidæminu fáum við bæði A og B oft. Eins ef við tökum lengd $2$ fáum við meðal annars AB oft. Fyrir $3$ kemur ABB tvisvar og fyrir $4$ kemur ABBA tvisvar fyrir. Það er ekki fyrir en loksins fyrir lengd $5$ sem við fáum ólíka hlutstrengi. Fáum ABBAA, BBAAB, BAABB, AABBA sem eru allir ólíkir.

ABBCD

2

ABBAABBA

5