Byteasar wants to put a rather long pattern on his house. In order to do this, he has to prepare an appropriate template with letters cut off first. He is going to put the pattern on the wall by putting the pattern on the wall in the appropriate place and painting over it. This way he can "print" all the letters that are on the template at one time (it is not possible to "print" only some of them). It is, however, possible, to paint some letters on the wall several times, as a result of different applications of the template. The letters on the template are adjacent (there are no spaces on it). Of course, it is possible to prepare a template with the whole pattern on it. But Byteasar would like to minimize the cost, so he wants to make a template as short as possible.
Write a programme that:
There are multiple test cases in the input file, one per line, and terminated by EOF. For each test case there is a string S (1<=|S|<=500,000) composited of lower-case letters of the English alphabet.
For each test case please print one integer indicates the minimum number of letters in the template.
ababbababbabababbabababbababbaba
ababbaba
ababbaba
ababbaba
ababbaba
ababbaba
8 8 8 8 8 8
Migrated from old NTUJ.
POI12th stage II
| No. | Testdata Range | Score |
|---|