2809번: 아스키 거리 - Aho-Corasick

모든 문자열을 입력받아 트라이를 만들면 메모리를 초과하므로, 몇 백개씩만 입력받아 트라이를 만들어 아호 코라식을 써야만 한다. 교체할 수 없는 타일의 개수는 최대한 긴 타일 묶음으로 타일을 교체할 때 남은 타일의 수와 같다.

특정 지점에서 최대한 긴 타일 묶음으로 교체하기 위해서는, 특정 지점에서의 타일 묶음의 길이의 최댓값을 구해야 한다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MAXN = 300000;
const int MAXTR = 1000001;
const int MAXAL = 26;
int N, M;
string street;

int node = 1;
const int root = 0;
int trie[MAXTR][MAXAL];
int exist[MAXTR];
int fail[MAXTR];
queue<int> qu;

int memo[MAXN];

void init()
{
    node = 1;
    memset(trie, -1, sizeof(trie));
    memset(exist, 0, sizeof(exist));
    memset(fail, -1, sizeof(fail));
}

void solve() //아호 코라식
{
    fail[root] = root;
    qu.push(root);
    while(!qu.empty())
    {
        int curNode = qu.front(); qu.pop();
        for(int i=0; i<MAXAL; i++)
        {
            int childNode = trie[curNode][i];
            if(childNode == -1) continue;
            
            int failNode = fail[curNode];
            if(curNode != root)
            {
                while(failNode != root && trie[failNode][i] == -1) failNode = fail[failNode];
                if(trie[failNode][i] != -1) failNode = trie[failNode][i];
            }
            
            fail[childNode] = failNode;
            //해당 노드에 놓을 수 있는 타일 길이의 최댓값을 구한다.
            if(exist[failNode]) exist[childNode] = max(exist[childNode], exist[failNode]);
            qu.push(childNode);
        }
    }
    
    int curNode = root;
    for(int i=0; i<N; i++)
    {
        char c = street[i];
        while(curNode != root && trie[curNode][c-'a'] == -1) curNode = fail[curNode];
        if(trie[curNode][c-'a'] != -1) curNode = trie[curNode][c-'a'];
        //해당 노드에 놓을 수 있는 타일 길이의 최댓값을 구한다.
        if(exist[curNode]) memo[i] = max(memo[i], exist[curNode]);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N;
    cin >> street;
    
    cin >> M;
    for(int i=1; i<=M; i++)
    {
        if(i % 200 == 1) init();
        
        string s; cin >> s;
        int curNode = root;
        for(char c : s)
        {
            if(trie[curNode][c-'a'] == -1) trie[curNode][c-'a'] = node++;
            curNode = trie[curNode][c-'a'];
        }
        //해당 노드에 놓을 수 있는 타일 길이의 최댓값을 구한다.
        exist[curNode] = max(exist[curNode], int(s.size()));

        if(i % 200 == 0 || i == M) solve(); //200개씩 끊어 트라이를 구현, 아호 코라식을 돌린다.
    }
    
    int ans = 0;
    int cnt = 0;
    for(int i=N-1; i>=0; i--)
    {
        cnt = max(cnt, memo[i]);
        if(!cnt--) ans++;
    }
    cout << ans;
}