#P11705. 「KTSC 2020 R1」字符串查找

「KTSC 2020 R1」字符串查找

题目背景

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

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

#include <bits/stdc++.h>

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

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

题目描述

对于由小写英文字母组成的两个字符串 AABB,当满足以下条件时,称这两个字符串实际上相同:

  1. AABB 的长度相同。
  2. 对于所有可能的整数 iijj,如果 AA 的第 ii 个字符和第 jj 个字符相同,则 BB 的第 ii 个字符和第 jj 个字符也相同。
  3. 对于所有可能的整数 iijj,如果 AA 的第 ii 个字符和第 jj 个字符不同,则 BB 的第 ii 个字符和第 jj 个字符也不同。

例如,A=abaA=a b aB=pqpB=p q p 是实际上相同的字符串。但是,A=abcaA=a b c aB=abcbB=a b c b 不是实际上相同的字符串。

编写一个程序,你将会得到字符串 TTPP,计算 TT 的连续子字符串中与 PP 实际上相同的子字符串的数量。

例如,T=abababbabT=a b a b a b b a bP=pqpP=p q pTT 中从左到右的子字符串 aba,bab,aba,bab,baba b a, b a b, a b a, b a b, b a b55 个与 PP 实际上相同。

你需要实现以下函数:

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

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

你需要提交一份代码,该代码中实现以下函数:

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

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

输入格式

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

  • 11 行:字符串 TT
  • 22 行:字符串 PP

输出格式

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

abababbab
pqp
5

提示

样例说明 #1

函数调用 返回值
findP("abababbab", "pqp", 9, 3) 5

数据范围

对于所有输入数据,满足:

  • 1N1061 \leq N \leq 10^6
  • 1MN1 \leq M \leq N

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

Subtask 分值 约束
11 88 N=MN=M
22 55 1N1001 \leq N \leq 100
33 1212 1N2,0001 \leq N \leq 2,000
44 7575 无附加限制