原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-D.html

题意

　　给定两个字符串，在根据给定的字符表转成相应的字符之后，问前一个串在后面一个串中匹配了多少次。

　　一个串在另一个串的某一个位置匹配，当且仅当从该位置起截取长度与那个串相同的一个子串，这个子串与那个串等价。

　　定义两个串等价，当且仅当这两个串的对应位置的 Ascll 码值相差不大于 1 。

　　任意一个串的长度 $\leq 250000$。

题解

　　FFT 基础套路题。

　　为了偷懒，我们写 11 次 DFT 。

　　但是这样做 double 精度不大行，long double 要超时。

　　所以我们用 NTT 来搞定。

　　注意别爆 long long 。

　　关于 FFT 和套路介绍，下面这个链接所指向的博文有详细介绍。

　　

　　

　　套路：

　　首先将第一个串翻转一下。

　　然后构造式子：

　　$f_i=\sum_{j=0}^{i} (S_i-T_j)^2((S_i-T_j)^2-1)$

　　展开之后 NTT 算出来就可以了。

代码

#include 
     
      using namespace std;typedef long long LL;const int N=1<<22,mod=998244353;int a,b,n,d;int S[N],T[N],R[N];char S1[N],T1[N];char s[27];int Pow(int x,int y){	int ans=1;	for (;y;y>>=1,x=1LL*x*x%mod)		if (y&1)			ans=1LL*ans*x%mod;	return ans;}int w[N],A[N];int A4[N],A3[N],A2[N],A1[N],A0[N];int B4[N],B3[N],B2[N],B1[N],B0[N];void FFT(int a[],int n){	for (int i=0;i
      
       >1,d=1;d
       
        <<=1,t>>=1)		for (int i=0;i
        
         <<1))			for (int j=0;j
         

vec;int main(){ scanf("%s%s%s",S1,T1,s); a=strlen(S1),b=strlen(T1); for (int i=0;i

>1]>>1)|((i&1)<<(d-1)); w[0]=1,w[1]=Pow(3,(mod-1)/n); for (int i=2;i