神奇的题目,真出在比赛里估计只能写hash
首先,看题面统计后缀前缀之类的东西,先想暴力hash(划掉
然后我们来说正解,看到这样字符串前缀后缀相等的题目自然会想到KMP
考虑到其是统计后缀,我先尝试了下把字符串reverse一下再看看能否统计,尝试后发现不行
然后考虑正常KMP的过程能否转化
发现对于一个i,正常KMP求出了最大匹配长度f[i],这是子串前缀匹配
尝试转化成后缀,自然想到匹配的是以i-f[i]+1开头的后缀,然而这个后缀可能并不是“最大”的,后面它可能还有后续,我们只能知道这次后缀匹配长度一定大于等于f[i]
然后是最难想的一步,由于我们只能统计答案中“大于等于某个值”的数量,所以考虑对答案求后缀和,即设cnt[i]为至少匹配了i这么长的后缀数量,询问时输出cnt[i] - cnt[i+1]
然后我们具体写出代码,发现对于一个i,需要累加所有能与它匹配的后缀,即f[i] nxt[f[i]] nxt[nxt[f[i]]] 一直到0, 这么跑下去复杂度又退化了,还不如直接写暴力,比上一步好想,考虑每次累加到一个匹配长度,那么它后面一直nxt到0的匹配长度都会被累加一次,所以我们再次利用差分的思想,直接在它身上加个1,最后累加起来即可,类似“区间修改”变成“两个单点修改” 。
本题正解有三步不是非常显然的转化,都需要有一定的“奇思妙想”,尤其是第二步,事实上难以想到(所以还是暴力hash部分分好
C++ 代码
#include <iostream>
#include <cstdio>
#define rint register int
#define lint long long
#define ull unsigned long long
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline void readint(tint& x) {
int f = 1; char ch = getchar(); x = 0;
for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
using namespace std;
const int maxn = 200000 + 10;
int n, m, t;
int snxt[maxn], f[maxn];
int cnt[maxn];
char s1[maxn], s2[maxn];
int main() {
readint(n), readint(m), readint(t);
scanf("%s %s", s1+1, s2+1);
for(rint i=2, j=0; i<=m; i++) {
while(j > 0 && s2[i] != s2[j+1]) j = snxt[j];
if(s2[i] == s2[j+1]) j++;
snxt[i] = j;
}
for(rint i=1, j=0; i<=n; i++) {
while(j > 0 && (j == m || s1[i] != s2[j+1])) j = snxt[j];
if(s1[i] == s2[j+1]) j++;
f[i] = j, cnt[j]++;
}
for(rint i=m; i>=1; i--) cnt[snxt[i]] += cnt[i];
int x = 0;
while(t--) readint(x), printf("%d\n", cnt[x] - cnt[x+1]);
return 0;
}
%%% dalao