Rotate String 字符串的思路

Problem Description
Counting strings has been an interesting thing for Mr. Frog since he was 6 years old. Whenever given a string s, Mr. Frog may tell you how many strings in the same length are lexicographically smaller than or equal to s. But now, as an university student, elementary questions may not arouse Mr. Frog’s interest, so a harder question appeared.

We call a string t representative string if t is the lexicographically smallest string in an equivalence class of strings under rotation. Given s, Mr. Frog wants to know how many representative strings t, in the same length as s, are lexicographically smaller than or equal to s. In order to be a magician, you may want to solve this challenge quickly to attract Mr. Frog’s attention.

Only those t consisting of lowercase letters should be considered.

Input
The first line contains only one integer T(T≤30), which indicates the number of test cases.

For each test case, there is only one line describing the given string s(1≤|s|≤100), s consists of lowercase letters.

Output
For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of representative strings to this question modulo 1000000007

Sample Input
2
bb
bab

Sample Output
Case #1: 27
Case #2: 651

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐