题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <bits/stdc++.h>

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

题目译自 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=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() 函数返回的值。

abababbab
pqp

5

提示

样例说明 #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$	无附加限制