P11705 「KTSC 2020 R1」字符串查找

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include int findP(char T[], char P[], int N, int M); ``` 题目译自 [2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2020/) T1「 [문자열 찾기](https://assets.ioikorea.kr/ioitst/2020/1/match/match_statement.pdf)」

对于由小写英文字母组成的两个字符串 $A$ 和 $B$，当满足以下条件时，称这两个字符串实际上相同： 1. $A$ 和 $B$ 的长度相同。 2. 对于所有可能的整数 $i$ 和 $j$，如果 $A$ 的第 $i$ 个字符和第 $j$ 个字符相同，则 $B$ 的第 $i$ 个字符和第 $j$ 个字符也相同。 3. 对于所有可能的整数 $i$ 和 $j$，如果 $A$ 的第 $i$ 个字符和第 $j$ 个字符不同，则 $B$ 的第 $i$ 个字符和第 $j$ 个字符也不同。 例如，$A=a b a$ 和 $B=p q p$ 是实际上相同的字符串。但是，$A=a b c a$ 和 $B=a b c b$ 不是实际上相同的字符串。 编写一个程序，你将会得到字符串 $T$ 和 $P$，计算 $T$ 的连续子字符串中与 $P$ 实际上相同的子字符串的数量。 例如，$T=a b a b a b b a b$ 和 $P=p q p$，$T$ 中从左到右的子字符串 $a b a, b a b, a b a, b a b, b a b$ 有 $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` 实际上相同的子字符串的数量。 你需要提交一份代码，该代码中实现以下函数： `int findP(char T[], char P[], int N, int M);` 该函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序按以下格式读取输入： - 第 $1$ 行：字符串 $T$ - 第 $2$ 行：字符串 $P$

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

### 样例说明 #1 | 函数调用 | 返回值 | | :----------: | :----------: | | `findP("abababbab", "pqp", 9, 3) ` | `5` | ### 数据范围 对于所有输入数据，满足： - $1 \leq N \leq 10^6$ - $1 \leq M \leq N$ 详细子任务附加限制及分值如下表所示。 | Subtask | 分值 | 约束 | | :----------: | :----------: | :----------: | |$1$|$8$|$N=M$| |$2$|$5$|$1 \leq N \leq 100$| |$3$|$12$|$1 \leq N \leq 2,000$| |$4$|$75$|无附加限制|