String rotations P62097


Statement
 

pdf   zip

html

Given a string s of size n, we define the i-th rotation of s (for 0 ≤ i < n) as

si si+1 … sn−1 s0 … si−2 si−1   .

Given two strings s and t, compute how many i-th rotations of s are equal to t.

For instance, for s = “abbabb” and t = “babbab” the answer is 2, corresponding to i = 2 and i = 5.

Input

Input consists of several cases, each one with two strings s and t with only lowercase letters. Assume 1 ≤ | s | = | t | ≤ 105. Every letter appears the same number of times in s and in t.

Output

For every case, print the number of i-th rotations of s that are equal to t.

Public test cases
  • Input

    abbabb babbab
    abc acb
    abba bbaa
    zzzzz zzzzz
    

    Output

    2
    0
    1
    5
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++