|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
G - Game of Matchings
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Adam and Carol are having a great time playing the Game of Matchings. The game is played on a string $S$ composed of $|S|$ lowercase English letters, $s_1 s_2 \dots s_{|S|}$. The goal is to find all matchings of a special kind of pattern $P$ in $S$. The pattern has length $N$ and is defined by a sequence of integers between $1$ and $26$.
We consider a contiguous substring $s_i s_{i+1} \dots s_{i+N-1}$ starting at position $i$ of $S$ a matching of pattern $P$ if there is a mapping from the numbers in $P$ to lowercase English letters such that the pattern is mapped to $s_i s_{i+1} ... s_{i+N-1}$ but no two distinct numbers are mapped to the same letter.
For instance, if $S$ is ''awawww'' and $P$ is $[10, 21, 10]$, the matchings of $P$ are the substrings of $S$ of length three starting at positions $1$ and $2$: ''awa'' and ''waw''. Note that ''www'' is not an occurence because pattern numbers $10$ and $21$ would both map to 'w'.
Adam and Carol lost the answer sheet and are not sure if they are finding all occurrences for some of the strings in the game. Given $S$ and $P$ can you find the number of matchings for them?
Input
The first line contains a non-empty string $S$ of at most $5 \times 10^5$ characters. Each character of $S$ is a lowercase English letter from $\texttt{a}$ to $\texttt{z}$. The second line contains an integer $N$ representing the size of the pattern ($1 \leq N \leq |S|$). The third line contains $N$ integers $P_1$, $P_2$, ..., $P_N$ denoting the pattern ($1 \leq P_i \leq 26$ for $i = 1,2, ..., N$).
Output
Output a line with one integer representing the number of matchings of $P$ found in $S$.
Sample test(s)
Input
awawww
3
10 21 10
Output
2
Input
abcdefghij
10
1 2 3 4 5 6 7 8 9 1
Output
0
Input
abbabaabbaababba
4
1 2 2 1
Output
5
Input
aabcddabccefkkgem
5
10 10 3 14 9
Output
4