阅读全文

03. Forgiving Matching题意：给出长度为n的原串S和模式串T，串由’1’,’2’,…,’9’和通配符’*’构成，问对于$k\in[0,n-1]$，S的子串中满足失配位置小于等于k的子串个数 用FFT/NTT卷积计算字符匹配数。单独考虑每个字符，如字符’1’，将S和T串根据位置上是否为’1’转化为一个0/1串，若$s[i]=t[j]=1$，则开始位置在$i-j+1$的子串匹配数+1，用数组$cnt[i]$记录开始位置在$i$的子串的匹配数，有$cnt[i]=\sum\limits_{j=1}^ns[j]t[j-i+1]$。 将T串反置为T’，即$t[j-i+1]=t’[n-(j-i+1)+1]=t’[n-j+i]$，就有$cnt[i]=\sum\limits_{j=1}^ns[j]t’[n-j+i]$，发现这个东西就可以用卷积计算了。$cnt[i]$的结果在卷积之后$n+i$的位置。 还需要注意的是通配符的处理，可以用一个容斥计算通配符的影响，将每个位置的结果直接加上两个串同通配符的总数，然后减去两个通配符相匹配的情况，两个通配符相匹配的情况计算方法同上。     阅读全文

P3808 【模板】AC自动机（简单版）     阅读全文

P3805 【模板】manacher 算法     阅读全文