题目描述

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1 「문자열 찾기」

对于由小写英文字母组成的两个字符串 $A$ 和 $B$，当满足以下条件时，称这两个字符串实际上相同：

1. $A$ 和 $B$ 的长度相同。
2. 对于所有可能的整数 $i$ 和 $j$，如果 $A$ 的第 $i$ 个字符和第 $j$ 个字符相同，则 $B$ 的第 $i$ 个字符和第 $j$ 个字符也相同。
3. 对于所有可能的整数 $i$ 和 $j$，如果 $A$ 的第 $i$ 个字符和第 $j$ 个字符不同，则 $B$ 的第 $i$ 个字符和第 $j$ 个字符也不同。

例如，$A=aba$ 和 $B=pqp$ 是实际上相同的字符串。但是，$A=abca$ 和 $B=abcb$ 不是实际上相同的字符串。

编写一个程序，接收字符串 $T$ 和 $P$，计算 $T$ 的连续子字符串中与 $P$ 实际上相同的子字符串的数量。

例如，$T=abababbab$ 和 $P=pqp$，$T$ 中从左到右的子字符串 $aba$, $bab$, $aba$, $bab$, $bab$ 有 $5$ 个与 $P$ 实际上相同。

实现细节

你需要实现以下函数：

int findP(char T[], char P[], int N, int M);

• $T$ 是长度为 $N+1$ 的数组（字符串）。
• $P$ 是长度为 $M+1$ 的数组。
• $T$ 和 $P$ 分别存储了长度为 $N$ 和 $M$ 的小写英文字母字符串。$T$ 和 $P$ 的最后一个位置存储了 \0。
• findP 函数返回 $T$ 的连续子字符串中与 $P$ 实际上相同的子字符串的数量。

你需要提交一个名为 match.cpp 的文件，该文件中实现以下函数：

int findP(char T[], char P[], int N, int M);

该函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：字符串 $T$
• 第 $2$ 行：字符串 $P$

示例评测程序将输出你的代码中 findP() 函数返回的值。

样例

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^6$
• $1 \leq M \leq N$

详细子任务附加限制及分值如下表所示。