Halloween Kemonomimi Party 2014

Problem C: Dog Girls

This morning, you woke up and realized that some dogs have turned into girls! In light of this exciting event, you immediately put on your wizard robes and walk outside, as everybody knows that dog-girls are magic users. Sure enough, one such sorceress is casting a spell on the street, and struck by awe, you gaze at her intently (so you can see what spell she's casting, of course).

For a dog-girl to use cast a spell, she must speak a magic word (which uniquely corresponds to that spell). A word S is magic if and only if |S| ≥ 2 and you can rotate it left by at least one but less than |S| positions such that the rotated word forms the original word. More formally, a word S is magic if and only if there exists an index i (0 < i < |S|) such that Si + j(mod|S|) = Sj (0 ≤ j < |S|) (the first letter of S is at index 0).

You hear the sorceress dog-girl mumble a long sequence of lowercase English letters, and you wonder what spell(s) she cast just now. Because you could not discern where the words began and end when she spoke, you will have to settle for finding out how many distinct spells she could have cast.

Input Format

The first and only line will have S, the sequence of letters the dog-girl mumbled (1 ≤ |S| ≤ 5000).
At least 10% of the test cases will have 1 ≤ |S| ≤ 100.
Another 15% of the test cases will have 1 ≤ |S| ≤ 400.
Another 25% of the test cases will have 1 ≤ |S| ≤ 1000.
Another 20% of the test cases will have 1 ≤ |S| ≤ 3000.

Output Format

The first and only line of output should contain the number of distinct substrings of S that are magic words.

Sample Input 1


Sample Output 1


Explanation for Sample 1

The whole string is a magic word abracadabracad. Additionally, no proper substring of abracadabracad is a magic word.

Sample Input 2


Sample Output 2


Explanation for Sample 2

The magic words are bb and cc.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: Nov 04, 2014
Author: FatalEagle

Languages Allowed:

Comments (Search)

It's quiet in here...