CF533F Encoding 題解

2021 年 3 月 13 日
筆記
CF

提示1：

\(\mathcal O(26^2*n)\) 的算法可通過。常用的幾種字符串匹配算法kmp，AC自動機，哈希都可以解決該問題（後兩者可以優化到 \(\mathcal O(26*n)\) ）。

提示2：

將文本串 \(S\) 和模式串 \(T\) 中的 \(26\) 個字母分開考慮，各自匹配。

\(\mathcal O(26^2*n)\) 的kmp匹配

枚舉每一種轉換，記為 \((x,y),x,y\in\{‘a’,’b’,\cdots,’z’\}\)，\(x\) 可以等於 \(y\) ，即不轉換。如果該轉換在某區間 \(S[l,r]\) 是與 \(T\) 匹配的，則說明在 \(S[l,r]\) 中每個 \(x\) 位置和 \(T\) 中 \(y\) 位置一一對應，每個 \(y\) 位置和 \(T\) 中 \(x\) 位置一一對應，而且不會有另一個關於 \(x\) 的轉換使得該區間匹配。若對於 \(S[l,r]\) 段上 \(x\) 的任何一種轉換都不能與 \(T\) 匹配，則說明該段無法匹配；否則在該區間起點打標記，表示該轉換匹配成功。對於 \(T\) 任何一個字符 \(x\) 都需要有轉換在 \(S[l,r]\) 中匹配，才說明 \(S[l,r]\) 是與 \(T\) 匹配的。

具體實現時令 \(T\) 中 \(x,y\) 互換，其他位置替換為 \(0\)，\(S\) 中除 \(x,y\) 以外的位置置為 0，其它保持不變，這樣可以用kmp判斷轉換 \((x,y)\) 是否與 \(S\) 上某一段匹配。例如：

	原字符串	轉換 \((b,c)\) ,變成只含 \(0,b,c\) 的序列（只在 \(T\) 轉換 \((b,c)\)）
\(S\)	\(abcab\)	\(0~b~c~0~b\)
\(T\)	\(acbac\)	\(0~b~c~0~b\)

這裡 \(a,b,c\) 都能找到轉換與 \(S\) 匹配（\(a\) 不轉換就可以匹配），而對於 \(S,T\) 都沒出現的字母，任意轉換都是匹配的，即會把兩個序列都變成全 \(0\) ，肯定是匹配的。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int sl,tl,nxt[N],ss[N],tt[N];
bool p[N][27];//p[i][j]標記S[i,i+tl-1]這段上是否有關於x的轉換使得與T串匹配
char s[N],t[N];
vector<int>ans;

int main() {
    scanf("%d %d %s %s",&sl,&tl,s+1,t+1);
    for(int x = 'a'; x <= 'z'; x++){
        for(int y = x; y <= 'z'; y++){
            //t中x，y互換
            for(int i = 1;i <= tl;i++) {
                if(t[i] == x) tt[i] = y;
                else if(t[i] == y) tt[i] = x;
                else tt[i] = 0;
            }
            for(int i = 1; i <= sl; i++) ss[i] = ( (s[i] == y)||(s[i] == x) )? s[i] : 0;

            //kmp匹配
            for(int i = 2,j = 0; i <= tl; i++){
                while(j && tt[i] != tt[j + 1]) j = nxt[j];
                if(tt[i] == tt[j + 1]) nxt[i] = ++j;
                else nxt[i] = 0;
            }
            for(int i = 1,j = 0; i <= sl; i++){
                while(j && ss[i] != tt[j + 1]) j = nxt[j];
                if(ss[i] == tt[j + 1]) ++j;
                if(j == tl) {
                    p[i-tl+1][x-'a'] = 1;
                    p[i-tl+1][y-'a'] = 1;
                    j = nxt[j];
                }
            }
        }
    }
    //O(26*n) 的判斷：S[i,i+tl-1]是否可以和轉換後的T匹配,要滿足t的每個字符j都有轉換與S[i,i+tl-1]匹配
    for(int i = 1;i <= sl-tl+1;i++) {
        int flag = 1;
        for(int j = 0;j < 26;j++) if(!p[i][j]) { flag = 0;break;}
        if(flag) ans.push_back(i);
    }
    printf("%d\n",ans.size());
    for(auto it : ans) printf("%d ",it);
    return 0;
}

\(\mathcal O(26*n)\) 的哈希匹配

在kmp匹配結束後，有一個 \(\mathcal O(26*n)\) 的判斷循環，因為在kmp中已經求出 \(p_{i,j}\) 的值了，所以對於每個 \(i\) ,有 \(26\) 次 \(\mathcal O(1)\) 的判斷。我們考慮，哈希也可以 \(\mathcal O(1)\) 的判斷兩個串是否匹配，這裡只要將 \(26\) 個字母分別求哈希值再求和匹配就可以了，所以哈希是可以將整體複雜度優化到 \(\mathcal O(26*n)\) 的。

具體實現時需要求出一個特殊的數組，我們記為 \(nxt_{i,j}\) ，表示 \(S[i,|s|]\) 上第一次出現字符 \(j\) 的下標。這樣在我們判斷 \(S[i,i+|t|-1]\) 這段區間是否可以通過轉換 \(j\) 使得與 \(T\) 匹配時，我們先通過 \(nxt_{i,j}\) 獲得 \(j\) 下標，如果它在 \([i,i+|t|-1]\) 這個區間上，說明它在 \(T\) 串對應位置有一個字符 \(y\) 需要與它匹配，如果我們把 \([i,i+|t|-1]\) 上的 \(j\) 全部替換為 \(y\) ，其他字符置為 \(0\) 。對所有的 \(26\) 個字符都這樣處理，他們分別計算的哈希值加起來與 \(T\) 的哈希值比較，就可以知道 \(S[i,i+|t|-1]\) 是否可以和 \(T\) 匹配了。這樣對於每個 \(i\) 的 \(26\) 次計算都是 \(\mathcal O(1)\) 的。注意對於同一區間上的字符轉換不能有交集，即兩個關於 \(x\) 的轉換 \((x,y),(x,z),y\not=z\) 不能同時存在，代碼中用 \(vis\) 記錄每個字符的轉換對象，每個字符的 \(vis_j\) 只能被賦值一次。~~因為比較懶沒寫雙哈希~~。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int base = 131;
const int mod = 19260817;
int sl,tl,nxt[N][26];
ll T_hash,s_hash[N][26],fac[N];
int vis[27];
vector<int>ans;
char s[N],t[N];

int main() {
    scanf("%d %d %s %s",&sl,&tl,s+1,t+1);
    fac[0] = 1;
    for(int i = 1;i <= sl;i++) fac[i] = fac[i-1] * base % mod;

    //預處理出nxt數組，記錄i後第一個字符j的下標
    for(int j = 0;j < 26;j++) nxt[sl+1][j] = sl+1;
    for(int i = sl;i >= 1;i--)
        for(int j = 0;j < 26;j++){
            if(s[i] == j+'a') nxt[i][j] = i;
            else nxt[i][j] = nxt[i+1][j];
        }

    //求出T串hash值
    for(int i = 1;i <= tl;i++) T_hash = (T_hash * base + (t[i]-'a') ) % mod;

    //求出S串26個字符分開計算的hash值，注意這裡是將為j的字符置為1，其他置為0作哈希，之後有（j,y)的轉換乘上y即可（哈希滿足乘法分配律）
    for(int i = 1;i <= sl;i++)
        for(int j = 0;j < 26;j++){
            if(s[i] == j+'a') s_hash[i][j] = (s_hash[i-1][j] * base + 1) % mod;
            else s_hash[i][j] = s_hash[i-1][j] * base % mod;
        }

    for(int i = 1;i <= sl-tl+1;i++) {
        ll tot_hash = 0;
        memset(vis,-1,sizeof vis); //-1表示未被賦值過
        for(int j = 0;j < 26;j++){
            int p = nxt[i][j];
            if(p > i + tl - 1) continue;
            int y = t[p-i+1]-'a';     //找到在T串對應位置的字符

            //只有之前x,y都沒有被轉換過才能賦值
            if(vis[j] == -1 && vis[y] == -1) vis[y] = j,vis[j] = y;
            tot_hash = (tot_hash + vis[j] * ((s_hash[i+tl-1][j] - s_hash[i-1][j] * fac[tl]) % mod + mod) ) % mod;
        }
        if(tot_hash == T_hash) ans.push_back(i);
    }
    printf("%d\n",ans.size());
    for(auto it :ans) printf("%d ",it);
    return 0;
}

\(\mathcal O(26*n)\) 的AC自動機匹配

思路來自【題解】Codeforces533F. Encoding 按字符分解，AC自動機。其實與哈希匹配思想是一致的，都是想要找到一種方式可以做到對於每個起點 \(i\) ，進行 \(26\) 次複雜度只有 \(\mathcal O(1)\) 的判斷。我們把 \(T\) 串分成 \(26\) 個 \(01\) 串（不計入全 \(0\) 串），構建AC自動機。再將 \(S\) 串分成 \(26\) 個 \(01\) 串，在AC自動機上作匹配，每次匹配到一個 \(T\) 串末尾，就在該位置標記匹配的字符，對於某個 \(i\) ,要求 \(T\) 中 \(26\) 個字符 \(j\) 都能被匹配到末尾（除 \(j\) 全 \(0\) 串外），才說明該段和 \(T\) 匹配。例如：

	原字符串	\(a\) 的 \(01\) 串	\(b\) 的 \(01\) 串	\(c\) 的 \(01\) 串
\(S\)	\(abcab\)	\(1~0~0~1~0\)	\(0~1~0~0~1\)	\(0~0~1~0~0\)
\(T\)	\(acbac\)	\(1~0~0~1~0\)	\(0~0~1~0~0\)	\(0~1~0~0~1\)

這裡 \(S\) 的 \(a\) 串會匹配到AC自動機上對應 \(T\) 的 \(a\) 串末端， \(S\) 的 \(b\) 串會匹配到AC自動機上對應 \(T\) 的 \(c\) 串末端， \(c\) 串會匹配到AC自動機上對應 \(T\) 的 \(b\) 串末端，其他全為 \(0\) 的串不插入AC自動機，所以 \(S\) 和 \(T\) 是匹配的。

AC自動機構建複雜度是 \(\mathcal O (26*n)\) 的，匹配時無需暴力跳fail，對於 \(26\) 個串的匹配也是 \(\mathcal O (26*n)\) 。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int sl,tl,tt[N],en[N*26], match[27];
bool has[27];
char s[N],t[N];
vector<int>ans;
int trie[N*26][2],cnt,fail[N*26],now[26];

void insert(int o){
    int now = 0;
    for (int i = 1,c; i <= tl;i++){
        c = tt[i];
        if(trie[now][c] == 0) trie[now][c] = ++cnt;
        now = trie[now][c];
    }
    en[now] = o;
}

void build(){
    queue<int> q;
    for (int i = 0; i < 2;i++) if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty()){
        int now = q.front();q.pop();
        for (int i = 0; i < 2;i++){
            if(trie[now][i]){
                q.push(trie[now][i]);
                fail[trie[now][i]] = trie[fail[now]][i];
            }else
                trie[now][i] = trie[fail[now]][i];
        }
    }
}

int main() {
    scanf("%d %d %s %s",&sl,&tl,s+1,t+1);
    memset(en,-1,sizeof en);
    for(int j = 0;j < 26;j++){
        for(int i = 1; i <= tl; i++)
            has[j] |= tt[i] = (t[i] == j + 'a');
        if(has[j]) insert(j); //不是全0串才插入AC自動機
    }
    build();
    for(int i = 1;i <= sl;i++){
        int flag = 0;
        memset(match,-1,sizeof match);
        for(int j = 0;j < 26;j++){
            int c = s[i]-'a';
            now[j] = trie[now[j]][c == j];
            if(en[now[j]] != -1) match[en[now[j]]] = j;//記錄T末端字符en[now[j]]匹配到S的字符j
        }
        for(int j = 0;j < 26;j++)
            if(has[j]){
                if(match[j] == -1) {flag = 1;break;}
                int y = match[j];
                //在T串同時含j,y的情況下，match[j]=y,match[y]=j才滿足變換後匹配
                if(match[y] != j && has[y]) {flag = 1;break;}  
            }
        if(!flag) ans.push_back(i-tl+1);
    }
    printf("%d\n",ans.size());
    for(auto it : ans) printf("%d ",it);
    return 0;
}

這道題可以用多種算法嘗試解決，是一道很全面的題目。各算法運行結果如下（空間換時間了）：

Tags: CF