G. Mutation

길이가 N인 문자열이 주어지고, 길이가 M인 패턴이 주어진다. 이 패턴의 연속된 일부분 혹은 전체를 한 번 뒤집어서 새로운 패턴들을 만들 수 있다. 길이가 N인 문자열에서 이렇게 만들어진 패턴들과 매치되는 부분 문자열이 몇 개인지 세어주는 문제다.

N ≤ 1,000,000 이고 M ≤ 100 이다. 시간제한은 0.2초로 N에 선형인 시간복잡도를 요구한다. 길이가 M인 패턴에서 뒤집는 연산에 의해 만들어지는 새로운 패턴의 개수는 많아야 $M^2$개다.

즉, 이 문제는 길이가 M인 패턴 $M^2$개와 길이가 N인 문자열을 매칭하는 문제로 바꿀 수 있다. 이와 관련된 문제는 Aho-Corasick 자료구조를 이용하면된다. KMP와 같은 문자열 매칭 알고리즘은 하나의 패턴과 전체 문자열을 매칭하는 알고리즘인데, Aho-Corasick은 여러 개의 패턴과 문자열 사이의 매칭을 선형 시간안에 가능하게 해준다.

일반적으로 Aho-Corasick을 구현할 때 까다로운 점은 문자열 사이의 포함 관계인데, 이 문제에서 모든 패턴은 서로 다르고 길이가 같기 때문에 포함 관계가 생기질 않는다. 이로 인해 Aho-Corasick에서 failure link만 잘 계산해주면 해결할 수 있다.

이 문제에서 Aho-Corasick을 구현하는 시간복잡도는 O(M^3)이고, 전체 문자열에 매칭이 되는지 확인해주는 시간복잡도는 O(N)이다. 따라서, 전체 시간복잡도는 O(N + M^3)으로 0.2초 안에 충분히 수행된다.

Aho-Corasick에 대한 자세한 설명은 생략하겠다. 연습 문제로는 문자열 집합 판별 문제가 있다.

#include <stdio.h> #include <string.h> #include <string> #include <vector> #include <queue> #include <algorithm> using namespace std; #define MAXN 1000006 #define MAXM 104 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() int T, N, M, K; char A[MAXN], B[MAXM]; int code[130]; string S; vector <string> list; struct NODE{ NODE(): v(0), f(0) { for (int i=0;i<4;i++) nxt[i] = 0; } bool v; NODE *nxt[4], *f; } *root, container[MAXN]; NODE *new_node() { NODE *ret = &container[K++]; ret->v = ret->f = 0; for (int i=0;i<4;i++) ret->nxt[i] = 0; return ret; } int main() { int i, j, k; code['C'] = 1, code['G'] = 2, code['T'] = 3; for (scanf("%d", &T);T--;){ scanf("%d%d%s%s", &N, &M, A+1, B+1); S = B+1; list.clear(); for (i=1;i<=M;i++){ for (j=i;j<=M;j++){ string s = S.substr(i-1, j-i+1); reverse(all(s)); s = S.substr(0, i-1)+s+S.substr(j, M-j); list.pb(s); } } sort(all(list)); list.erase(unique(all(list)), list.end()); K = 0; root = new_node(); for (const string &s: list){ NODE *now = root; for (j=0;j<M;j++){ int c = code[s[j]]; if (!now->nxt[c]) now->nxt[c] = new_node(); now = now->nxt[c]; } now->v = 1; } queue <NODE*> que; for (i=0;i<4;i++) if (root->nxt[i]){ root->nxt[i]->f = root; que.push(root->nxt[i]); } while (!que.empty()){ NODE *q = que.front(); que.pop(); NODE *f = q->f; for (i=0;i<4;i++) if (q->nxt[i]){ NODE* &nf = q->nxt[i]->f; nf = f; while (nf != root && !nf->nxt[i]) nf = nf->f; if (nf->nxt[i]) nf = nf->nxt[i]; que.push(q->nxt[i]); } } NODE *now = root; int ans = 0; for (i=1;i<=N;i++){ int c = code[A[i]]; while (now != root && !now->nxt[c]) now = now->f; if (now->nxt[c]) now = now->nxt[c]; if (now->v) ans++, now = now->f; } printf("%d\n", ans); } }