0. 前言

记录做题中遇见的一些好玩的科技。

1. 含通用符的字符串匹配问题

在没有通用符的字符串匹配问题中，我们一般使用O(n+m)O(n+m) 的 KMP，多模匹配下我们会考虑 AC 自动机。但是，我们还有令玩意中做法：

设P(x)=∑i=0m−1(Ai−Bx+i)P(x)=\sum\limits_{i=0}^{m-1} (A_{i}-B_{x+i})。

但是Ai−Bx+iA_{i}-B_{x+i} 是没有正负性这一说的，所以我们要将其平方，有：

P(x)=∑i=0m−1(Ai−Bx+i)2=∑i=0m−1(Ai2−2AiBx+i+Bx+i2)\begin{aligned} P(x) & =\sum\limits_{i=0}^{m-1} (A_{i}-B_{x+i})^2 \\ & =\sum\limits_{i=0}^{m-1} (A_{i}^2-2A_{i}B_{x+i}+B_{x+i}^2) \end{aligned}

其中Ai2,Bx+i2A_{i}^2,B_{x+i}^2 可以快速预处理，但是AiBx+iA_{i}B_{x+i} 不太好处理。一般对于这种式子需要改写成卷积的形式，不妨将AA 反转，那么匹配函数P(x)=∑i=0m−1(Am−i−12−2Am−i−1Bx−m+i−1+Bx−m+i+12)P(x)=\sum\limits_{i=0}^{m-1}(A_{m-i-1}^2 - 2A_{m-i-1}B_{x-m+i-1}+B_{x-m+i+1}^2)。发现Am−i−1Bx−m+i+1A_{m-i-1}B_{x-m+i+1} 是卷积形式，用 FFT 求解，时间复杂度为O(nlog⁡n)O(n \log n)。

P4173 残缺的字符串

这题出现了可以代替一个字符的通用符，可以将通用符的权值设为 0，再乘上权值即可。

P(x)=∑i=0m−1(Am−i−1−Bx−m+i+1)2Am−i−1Bx−m+i+1=∑i=0m−1(Am−i−13Bx−m+i+1−2Am−i−12Bx−m+i+12+Am−i−1Bx−m+i+13)\begin{aligned} P(x)&=\sum\limits_{i=0}^{m-1} (A_{m-i-1}-B_{x-m+i+1})^2A_{m-i-1}B_{x-m+i+1} \\ & =\sum\limits_{i=0}^{m-1} (A_{m-i-1}^3B_{x-m+i+1}-2A_{m-i-1}^2B_{x-m+i+1}^2+A_{m-i-1}B_{x-m+i+1}^3) \end{aligned}

做三次 FFT 即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e7+15,MR=MN<<2;
const double pi=acos(-1);
using compd=complex<double>;
int n,m,len,s[MN],tot;
int rev[MN],A[MN],B[MN];
compd a[MN],b[MN],ans[MN];
string s1,s2;

void dorev(compd f[],int len){
    for(int i=0;i<len;i++){
        rev[i]=rev[i>>1]>>1;
        if(i&1){
            rev[i]|=len>>1;
        }
    }
    for(int i=0;i<len;i++){
        if(i<rev[i]) swap(f[i],f[rev[i]]);
    }
}

void fft(compd f[],int len,int mode){
    dorev(f,len);
    for(int i=2;i<=len;i<<=1){//处理的区间长度
        compd wn(cos(2*pi/i),sin(2*pi*mode/i));
        for(int j=0;j<len;j+=i){//步长为i
            compd w(1,0);
            for(int k=j;k<j+i/2;k++){// 蝶形优化
                compd u=f[k];//左区间
                compd t=w*f[k+i/2];//右区间
                f[k]=u+t;
                f[k+i/2]=u-t;
                w=w*wn;
            }
        }
    }
    if(mode==-1){
        for(int i=0;i<len;i++){
            f[i]/=len;
        }
    }
}

signed main(){
    cin>>m>>n>>s1>>s2;
    reverse(s1.begin(),s1.end());
    len=1;
    while(len<=n+m) len<<=1;
    for(int i=0;i<m;i++){
        A[i]=(s1[i]!='*')?(s1[i]-'a'+1):0;
    }
    for(int i=0;i<n;i++){
        B[i]=(s2[i]!='*')?(s2[i]-'a'+1):0;
    }
    for(int i=0;i<=len;i++){
        a[i]=compd(A[i]*A[i]*A[i],0);
        b[i]=compd(B[i],0);
    }
    fft(a,len,1);
    fft(b,len,1);
    for(int i=0;i<=len;i++) ans[i]=ans[i]+a[i]*b[i];
    for(int i=0;i<=len;i++){
        a[i]=compd(A[i],0);
        b[i]=compd(B[i]*B[i]*B[i],0);
    }
    fft(a,len,1);
    fft(b,len,1);
    for(int i=0;i<=len;i++) ans[i]=ans[i]+a[i]*b[i];
    for(int i=0;i<=len;i++){
        a[i]=compd(A[i]*A[i],0);
        b[i]=compd(B[i]*B[i],0);
    }
    fft(a,len,1);
    fft(b,len,1);
    for(int i=0;i<=len;i++) ans[i]=ans[i]+a[i]*b[i]*compd(-2,0);
    fft(ans,len,-1);
    for(int i=m-1;i<n;i++){
        if(fabs(ans[i].real())<=0.5) s[++tot]=i-m+2;
    }
    cout<<tot<<'\n';
    for(int i=1;i<=tot;i++) cout<<s[i]<<" ";
    return 0;
}

2.关于位置对称的问题

P4199 万径人踪灭

设fi=∑j=0i[sj=s2×i−j]f_i=\sum\limits_{j=0}^i [s_j=s_{2\times i-j}]。

如果不管不能是连续的一段的限制，那么每一个ii 的答案就是2fi−12_{f_i}-1。

是连续的一段的限制直接用 Manacher 做（其实也可以二分+哈希）。

发现fi=∑j=0i[sj=s2×i−j]f_i=\sum\limits_{j=0}^i [s_j=s_{2\times i-j}] 是卷积形式。

设aia_i 表示sis_i 是否为 a，bib_i 表示sis_i 是否为 b。

那么f=a∗a+b∗bf=a*a+b*b。

FFT 直接做即可，时间复杂度O(nlog⁡n)O(n\log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
#define int long long
using namespace std;
using compd=complex<double>;
constexpr int MN=3e5+15,MOD=1e9+7;
int n,x[MN],p[MN],s[MN],ans[MN],ret;
string st;
compd A[MN],B[MN];

namespace PolyFFT{
    const double pi=acos(-1);
    constexpr int MXREV=1e6;
    using compd=complex<double>;

    int rev[MXREV];

    void dorev(compd f[],int len){
        for(int i=0;i<len;i++){
            rev[i]=rev[i>>1]>>1;
            if(i&1){
                rev[i]|=len>>1;
            }
        }
        for(int i=0;i<len;i++){
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
    }

    void fft(compd f[],int len,int mode){
        dorev(f,len);
        for(int i=2;i<=len;i<<=1){//处理的区间长度
            compd wn(cos(2*pi/i),sin(2*pi*mode/i));
            for(int j=0;j<len;j+=i){//步长为i
                compd w(1,0);
                for(int k=j;k<j+i/2;k++){// 蝶形优化
                    compd u=f[k];//左区间
                    compd t=w*f[k+i/2];//右区间
                    f[k]=u+t;
                    f[k+i/2]=u-t;
                    w=w*wn;
                }
            }
        }
        if(mode==-1){
            for(int i=0;i<len;i++){
                f[i]/=len;
            }
        }
    }
    
    // F is the out ans
    void Mul(compd F[],compd G[],int n,int m){
        int len=1;
        while(len<=n+m) len<<=1;
        fft(F,len,1);
        fft(G,len,1);
        for(int i=0;i<len;i++) F[i]=F[i]*G[i];
        fft(F,len,-1);
    }

    // Ans is the out,The second state is the len
    pair<compd*,int> MulAns(compd F[],compd G[],compd Ans[],int n,int m){
        int len=1;
        while(len<=n+m) len<<=1;
        fft(F,len,1);
        fft(G,len,1);
        for(int i=0;i<len;i++) Ans[i]=F[i]*G[i];
        fft(Ans,len,-1);
        return pair<compd*,int>(Ans,len);
    }
}

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}

void manacher(){
    int r=0,c=0;
    for(int i=1;i<=(n<<1)+1;i++){
        if(i<r) p[i]=min(p[c*2-i],r-i);
        else p[i]=1;
        while(x[i+p[i]]==x[i-p[i]]) p[i]++;
        if(p[i]+i>r){
            r=p[i]+i;
            c=i;
        }
    }
}

signed main(){
    cin>>st;
    n=st.length();
    for(int i=0;i<n;i++) s[i+1]=(st[i]=='a');
    for(int i=1;i<=(n<<1)+1;i++){
        if(i&1) x[i]=2;
        else x[i]=s[i>>1];
    }
    x[0]=-1,x[(n+1)<<1]=-2;
    for(int i=1;i<=n;i++){
        A[i]=B[i]=compd(s[i],0);
    }
    PolyFFT::Mul(A,B,n,n);
    for(int i=1;i<=(n<<1)+1;i++){
        ans[i]+=(llround(A[i].real())-((i&1)^1));
    }
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
    for(int i=1;i<=n;i++){
        A[i]=B[i]=compd((s[i]^1),0);
    }
    PolyFFT::Mul(A,B,n,n);
    for(int i=1;i<=(n<<1)+1;i++){
        ans[i]+=(llround(A[i].real())-((i&1)^1));
    }
    for(int i=1;i<=(n<<1)+1;i++){
        ans[i]=((ans[i]+((i&1)^1))>>1)+((i&1)^1);
    }
    for(int i=1;i<=(n<<1)+1;i++){
        ans[i]=(ksm(2,ans[i])-1+MOD)%MOD;
    }
    manacher();
    for(int i=1;i<=(n<<1)+1;i++){
        ans[i]=(ans[i]-(p[i]>>1)+MOD)%MOD;
    }
    for(int i=1;i<=(n<<1)+1;i++){
        (ret+=ans[i])%=MOD;
    }
    cout<<ret;
}