2809_아스키거리

진짜 극혐... 어제부터 계속 붙잡고 있었다.

딱히 붙잡고 있을만큼 영양가 있는 문제는 아니었는데

이게 풀이가 suffix array랑 아호코라식 두개가 있는데 suffix 풀이가 궁금해서 내가 그나마 풀 수 있는 아호코라식으로 열심히 비벼봄..ㅠ

coci에 솔루션은 있는데 정답 코드가 없다.

일단 나는 보자마자 아호코라식이 생각나서 그걸로 접근했다-> 26*4*5000*5000하면 당연히 메모리 터짐

그냥 Trie면 내가 아름다운 이름을 푼 방식이나 그렇게 접근할텐데

아호코라식이라 queue에서 bfs를 돌 때 구하기 좀 빡세서.. 쥬륵

map으로 해봐도 안되고 -> 근데 아름다운 이름에서도 map을 써본 결과 map은 딱히 메모리를 엄청나게 줄여주진 않는 거 같다. 얘는 쓸때마다 터짐

결국 질문검색에서 찾다가 vector + bitmask를 쓰신 분이 있길래 한 번 해보기나 하자 하고 짜봤다.

극혐~메모리 최적화~극혐

+)

https://www.acmicpc.net/source/6463084

suffix array 코드를 찾다가 다른 코드는 이해불가능인데 친절하게 설명을 써놓으셨고 코드도 가독성 좋게 잘 짜셔서 이해할 수 있었다..!

이게 sa 정해인 것 같다 갓..갓..

#include <iostream>
#include <string.h>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define MAX 100001
 
int N, M;
int mark[300001], chk[300001];
string str2;
char str[300002];
 
//1. n번째가 어떤 문자인지
//2. 현재 문자가 존재하는지
//3. 어떤 문자가 몇번째에 존재하는지
 
int isexist(int& exist, int ch) { //현재 문자가 존재하는지
    return (exist & (1 << (25-ch)));
}
 
int whatch(int& exist, int ch) { //ch가 몇번째에 존재하는지
    int cnt = 0;
    for (int i = 0; i < ch; ++i) {
        if (exist & (1 << (25 - i))) cnt++;
    }
    return cnt;
}
 
int nthch(int& exist, int n) {  //n번째 문자가 뭐인지
    int cnt = 0;
    for (int i = 0; i < 26; ++i) {
        if (exist & (1 << (25 - i))) {
            if (cnt == n) return i;
            cnt++;
        }
    }
    return -1;
}
 
struct Trie {
    vector<Trie*> next;
    Trie* fail;
    int output;
    int exist;
    Trie() {
        fail = nullptr;
        output = exist = 0;
    }
    ~Trie() {
        for (int i = 0; i < next.size(); ++i) {
            delete next[i];
        }
    }
 
    void insert(const char* key, int len) {
        if (*key == '\0') {
            if (output < len) {
                output = len;
            }
        }
        else {
            int cur = *key - 'a';
            int n = whatch(exist, cur);
            if (!isexist(exist, cur)) {
                exist |= (1 << (25 - cur));
                next.insert(next.begin() + n, new Trie());
            }
            next[n]->insert(key + 1, len);
        }
    }
};
 
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    //freopen("poplocavanje.in.3", "r", stdin);
    Trie* root = new Trie();
 
    cin >> N;
    cin >> str;
    
 
    cin >> M;
    for (int i = 0; i < M; ++i) {
        cin >> str2;
        if (str2.length() > N) continue;
        root->insert(&str2[0], str2.length());
    }
 
    queue<Trie*> q;
    root->fail = root;
    q.push(root);
    while (!q.empty()) {
        Trie* curr = q.front(); q.pop();
 
        for (int i = 0; i < curr->next.size(); ++i) {
            Trie* next = curr->next[i];
 
            if (curr == root) next->fail = root;
            else {
                int nthCh = nthch(curr->exist, i); //curr에서 i번째가 어떤 문자인지
                Trie* desc = curr->fail;
                //desc에 nthCh가 있을 때까지
                while (desc != root && !isexist(desc->exist, nthCh))
                    desc = desc->fail;
 
                //desc에 nthCh가 존재하는 경우
                //desc의 배열에 몇번째에 nthCh가 존재하는지
                if (isexist(desc->exist, nthCh))
                    desc = desc->next[whatch(desc->exist, nthCh)];
                next->fail = desc;
            }
            if (next->fail->output) {
                if (next->output < next->fail->output) {
                    next->output = next->fail->output;
                }
            }
            q.push(next);
        }
    }
 
    Trie* curr = root;
    for (int c = 0; str[c]; ++c) {
        int next = str[c] - 'a';
        while (curr != root && !isexist(curr->exist, next))
            curr = curr->fail;
        if (isexist(curr->exist, next)) curr = curr->next[whatch(curr->exist, next)];
        if (curr->output) {
            mark[c] = max(mark[c], curr->output);
        }
    }
 
    int res = 0;
    for (int i = N - 1; i >= 0; --i) {
        int check = mark[i];
        if (check == 0 && chk[i] == 0) res++;
        while (chk[i - check + 1] == 0 && i - check + 1 <= i) {
            chk[i - check + 1] = 1;
            check--;
        }
    }
 
    cout << res;
    delete root;
}