Anagram Windows

Difficulty: 1500 3000 ms 128 MB

strings sliding-window

Count the substrings of T that are anagrams (permutations) of P.

Input: two lines: the text T, then the pattern P.

Output: the number of anagram occurrences.

Constraints:

• 1 ≤ |T| ≤ 10⁵
• 1 ≤ |P| ≤ |T|
• lowercase letters

Sample Tests

abab
ab

3

aaa
aa

2

Read the Editorial