E - Searching in a Circular String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は、文字列の検索アルゴリズムの研究をしています。今回のテーマは、円環状の文字列に対するパターンマッチングです。

英小文字からなる文字列 S が与えられます。S の長さを N とします。この文字列は円環状に並んでいるものとみなします。すなわち、S の末尾の次には再び先頭の文字が続くものとします。

また、英小文字からなるパターン文字列 T が与えられます。T の長さを M とします。

S の各文字の位置を 0, 1, \ldots, N-1（0-indexed）で表します。各位置 i（0 \leq i < N）に対して、位置 i を開始位置として円環上で連続する M 文字を順に読んだ文字列 R_i を次のように定義します。各 j（0 \leq j < M）に対して、R_i の j 文字目（0-indexed）は S の位置 (i + j) \bmod N の文字です。

なお、この定義は M > N の場合にもそのまま適用されます。その場合は円環を複数周回することになり、同じ位置の文字が繰り返し参照されます。

N 個の開始位置 i = 0, 1, \ldots, N-1 のそれぞれについて R_i = T であるかを判定し、R_i = T となる開始位置の個数を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq M \leq 5 \times 10^5
  • S は英小文字のみからなる長さ N の文字列
  • T は英小文字のみからなる長さ M の文字列

入力

S
T
  • 1 行目には、文字列 S が与えられる。
  • 2 行目には、パターン文字列 T が与えられる。

出力

円環状の文字列 S においてパターン文字列 T と一致する開始位置の個数を 1 行で出力せよ。

入力例 1

ababc
abc

出力例 1

1

入力例 2

abc
bcab

出力例 2

1

入力例 3

abracadabracadabra
cadabra

出力例 3

2

入力例 4

abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
deabcdeabcdeabcdeabcdeabc

出力例 4

20

入力例 5

a
a

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is researching string search algorithms. His current topic is pattern matching on circular strings.

You are given a string S consisting of lowercase English letters. Let N be the length of S. This string is considered to be arranged in a circular manner. That is, the first character follows immediately after the last character of S.

You are also given a pattern string T consisting of lowercase English letters. Let M be the length of T.

The positions of each character in S are represented as 0, 1, \ldots, N-1 (0-indexed). For each position i (0 \leq i < N), define the string R_i as the string obtained by reading M consecutive characters on the circle starting from position i. Specifically, for each j (0 \leq j < M), the j-th character (0-indexed) of R_i is the character at position (i + j) \bmod N in S.

Note that this definition applies even when M > N. In that case, the circle is traversed multiple times, and characters at the same position are referenced repeatedly.

For each of the N starting positions i = 0, 1, \ldots, N-1, determine whether R_i = T, and find the number of starting positions where R_i = T.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq M \leq 5 \times 10^5
  • S is a string of length N consisting of lowercase English letters only
  • T is a string of length M consisting of lowercase English letters only

Input

S
T
  • The first line contains the string S.
  • The second line contains the pattern string T.

Output

Output in one line the number of starting positions in the circular string S that match the pattern string T.

Sample Input 1

ababc
abc

Sample Output 1

1

Sample Input 2

abc
bcab

Sample Output 2

1

Sample Input 3

abracadabracadabra
cadabra

Sample Output 3

2

Sample Input 4

abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
deabcdeabcdeabcdeabcdeabc

Sample Output 4

20

Sample Input 5

a
a

Sample Output 5

1