Halloween '14 P3 - Dog Girls

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.4s
Memory limit: 256M
Author:
FatalEagle
Problem types

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| \ge 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 S_{(i+j) \bmod |S|} = S_j (0 \le 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 ended when she spoke, you will have to settle for finding out how many distinct spells she could have cast.

Input Specification

The first and only line will have S, the sequence of letters the dog-girl mumbled (1 \le |S| \le 5000).

At least 10% of the test cases will have 1 \le |S| \le 100.

Another 15% of the test cases will have 1 \le |S| \le 400.

Another 25% of the test cases will have 1 \le |S| \le 1000.

Another 20% of the test cases will have 1 \le |S| \le 3000.

Output Specification

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

Sample Input 1

abracadabracad

Sample Output 1

1

Explanation for Sample Output 1

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

Sample Input 2

abbccbba

Sample Output 2

2

Explanation for Sample Output 2

bb and cc are magic words.

Comments


  • 3
    Evanhyd  commented on May 14, 2022, 5:07 a.m. ← edited

    add

    $(function() { $(".anime-img").show(); });

    to your dmoj user script, and then refresh the page


  • 17
    echofox  commented on April 23, 2018, 1:19 p.m.

    protip: don't open this question in public


    • 6
      pblpbl  commented on March 26, 2020, 8:57 p.m.

      i needed to read this before scrolling past it


  • -28
    kobortor  commented on Feb. 22, 2016, 11:43 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 7
      d  commented on Feb. 28, 2016, 12:39 a.m.

      Just use the prime number 2^{53}+5.