VM 08 Bài 21 - Xử lý xâu

View as PDF

Submit solution

Points: 0.94 (partial)
Time limit: 0.6s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 8/DivAProblem Setter: Yang Yi
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~2~ xâu ~S~ và ~T~ có cùng độ dài ~N~. Bạn được thực hiện lần lượt ~2~ thao tác trên xâu ~S~, theo đúng thứ tự:

  • Chọn ~1~ vị trí của ~S~ và thay thế bằng ký tự bất kỳ
  • Xoay chuỗi ~S~ theo vòng tròn. Nghĩa là chọn ~1~ vị trí ~k~ và dịch chuỗi ~S~ theo vòng tròn sao cho ~k~ trở thành vị trí bắt đầu của chuỗi mới. Chú ý nếu ~k~ = ~0~ thì chuỗi không thay đổi.

Đếm số cách áp dụng ~2~ thao tác trên để biến xâu ~S~ thành xâu ~T~.

Input

Gồm ~2~ xâu ~S~ và ~T~, chỉ gồm các ký tự in hoa. Độ dài không quá ~10^{5}~.

Output

Gồm ~1~ số nguyên duy nhất là số cách biến đổi.

Sample Input 1

AHYANGYI YANGYIAH

Sample Output 1

8

Sample Input 2

VSUMSU MSUMSU

Sample Output 2

2

Note

Test ~1~

  • Có thể thay chữ "A" đầu bằng "A", chữ "H" bằng "H", ... (~8~ cách thay đổi)
  • Sau đó, có duy nhất 1 cách dịch chuyển chuỗi.

Test ~2~

  • Cần thay thế chữ "V" đầu thành chữ "M"
  • Sau đó có ~2~ cách dịch chuyển ~k = 0~ hoặc ~k = 3~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.