Acwing周赛42 (KMP，偷偷拿字符串哈希水过去了)

题目 题意: 分别给出长度为n和m的字符串a、b，有q次询问，询问在字符串a的[l,r]中出现了多少次b。 思路: KMP匹配一下，然后维护一下前缀和，即可O(1)查询。 时间复杂度: O(n+q) 代码:

// Problem: 出现次数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4315/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>n>>m>>q;
   cin>>(s+1); cin>>(p+1);
   for(int i=2,j=0;i