Synchronous Echo#13118
You are given two strings and consisting of lowercase English letters.
For a nonempty string , let p_1<p_2<\ldots<p_k be all starting positions of its occurrences in , and let q_1<q_2<\ldots<q_m be all starting positions of its occurrences in . Positions are numbered starting from .
We call synchronous if k=m\ge 3 and there is an integer such that
In other words, shifting all occurrences of in one string by the same amount makes them coincide with all its occurrences in the other string. The shift may be positive, negative, or zero, and may differ for different strings .
Find the number of distinct nonempty synchronous strings. Two strings are distinct if they have different lengths or differ in at least one character. Occurrences may overlap.
The first line contains , and the second line contains (1\le |s|,|t|\le 2\cdot 10^5). Both strings contain only lowercase English letters.
Print one integer — the number of distinct nonempty synchronous strings.
Beispiel 1
Beispiel 2
Beispiel 3
In the first example, the six suitable strings are a, b, c, ab, bc, and abc. In particular, abc occurs in at positions and in at positions , so its shift is d=1.
In the second example, a occurs three times in each string, but its starting positions are and . No single shift makes these sets coincide. No other string occurs at least three times in both strings.
In the third example, the suitable strings are a, aa, and aaa.
Subtask ( points): |s|,|t|\le 12.
Subtask ( points): |s|,|t|\le 100.
Subtask ( points): |s|,|t|\le 2000.
Subtask ( points): s=t.
Subtask ( points): \min(|s|,|t|)\le 200.
Subtask ( points): no additional constraints.