TIOJ-1035

,

通關密語

https://tioj.ck.tp.edu.tw/problems/1035

Description

給定兩個長度小於 $5 \times 10^4$ 的小寫英文字母字串 $S,T$
定義「最佳擬合」，就是將 $S$ 經過平移後和 $T$ 比對，同樣的字元數最多的那一種方法。
請輸出一個正整數，代表最佳擬合的方案下，相同的字元有幾個。

ex.
對於

ababa
babab

來說，

ababa
=babab

這是一種最佳擬合的方法，$S$經過向左平移之後$S,T$有四個位置的字元相同

Solution

naive的$n^2$做法可以AC本題，只要妥當控制常數即可
不過這裡提供一個NTT的$\mathcal{O}(C\cdot n\log n)$解

假設$S$對$T$的平移量是$x$(可以為負的)，題目所求為

$$
\sum _ {i-j = x} [S_i = T_j]
$$

的最大值

那我們枚舉26種英文字母，可以寫成

$$
\sum _ {c \in \sigma} \sum _ {i-j = x} [S_i = c] \cdot [T_j = c]
$$

令$F_i = [S_i = c], G_j = [T _ {-j} = c]$
答案便是

$$
R_x = \sum _ {i+j = x} F_i G_j = F * G
$$

最後取$R$的最大值就好了，答案不會大於字串長度所以模數只要不要超小就不用關心答案被mod到
每次捲積交給NTT可以$\mathcal{O}(n\log n)$做完

索引值取負號可以用直接反轉字串取代，因為本題不關心偏移量$x$是多少
另外這題用FFT好像比較快，模的常數真的有點大
有一個常數優化是沒有出現過的字母就不需要NTT

AC code

 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

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
using namespace std;
const int64_t m = 998244353, g = 3, N = 1<<17;
int rev[N];
int64_t modpow(int64_t e,int64_t p) {
    int64_t r = 1;
    while(p) (p&1)&&(r=r*e%m), e=e*e%m, p>>=1;
    return r;
}
void NTT(int64_t F[],int n,bool inv) {
    for(int i = 0, L = __lg(n); i < n; i++) {
        rev[i] = (rev[i>>1]>>1) | ((i&1)<<L-1);
        if(i < rev[i]) swap(F[i],F[rev[i]]);
    }
    for(int step = 1; step < n; step *= 2) {
        int64_t root = modpow(g,(m-1)/(step*2));
        if(inv) root = modpow(root,m-2);
        for(int i = 0; i < n; i += step*2) {
            int64_t now = 1;
            for(int j = 0; j < step; j++) {
                int64_t a = F[i+j];
                int64_t b = F[i+j+step]*now%m;
                F[i+j] = (a+b)%m;
                F[i+j+step] = (a-b+m)%m;
                now = now*root%m;
            }
        }
    }
    if(inv) {
        int64_t in = modpow(n,m-2); // inv of n
        for(int i = 0; i < n; i++) F[i] = F[i]*in%m;
    }
}
void mul(int64_t A[],int64_t B[],int64_t C[],int n) {
    NTT(A,n,0);
    NTT(B,n,0);
    for(int i = 0; i < n; i++) C[i] = A[i]*B[i]%m;
    NTT(C,n,1);
}
int64_t A[N],B[N],C[N],ans[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s,t;
    cin >> s >> t;
    int n = 1<<__lg(s.size()+t.size())+1;
    for(int c = 0; c < 26; c++) {
        for(int i = 0; i < n; i++) {
            A[i] = (i < s.size() && s[i]-'a'==c);
            B[i] = (i < t.size() && t[t.size()-1-i]-'a'==c);
        }
        mul(A,B,C,n);
        for(int i = 0; i < n; i++) ans[i] += C[i];
    }
    cout << *max_element(ans,ans+n) << '\n';
}
comments powered by Disqus