oVeron

모든 문자열을 입력받아 트라이를 만들면 메모리를 초과하므로, 몇 백개씩만 입력받아 트라이를 만들어 아호 코라식을 써야만 한다. 교체할 수 없는 타일의 개수는 최대한 긴 타일 묶음으로 타일을 교체할 때 남은 타일의 수와 같다.특정 지점에서 최대한 긴 타일 묶음으로 교체하기 위해서는, 특정 지점에서의 타일 묶음의 길이의 최댓값을 구해야 한다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 300000;const int MAXTR = 1000001;const int MAXAL = 26;int N, M;string street;int node = ..

알고리즘/baekjoon 2024. 8. 12. 20:19

marker의 돌연변이 구조를 전부 만들고 Trie에 저장, 아호 코라식으로 DNA 구조를 확인하면 된다.돌연변이 구조를 만들 때 구현에 유의하자.메모리가 생각보다 빡빡해서 A, C, G, T만 자식으로 저장해야 한다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXTR = 1000001;const int MAXAL = 4;int N, M;string DNA, marker;int node = 1;int root = 0;int trie[MAXTR][MAXAL];bool exist[MAXTR];int fail[MAXTR];queue qu;void in..

알고리즘/baekjoon 2024. 8. 12. 17:22

Aho-Corasick 기본 문제.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXTR = 100001;const int MAXAL = 26;int N, M;int node = 1;int trie[MAXTR][MAXAL];bool exist[MAXTR];int fail[MAXTR];int root = 0;queue qu;int main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); memset(trie, -1, sizeof(trie)); memset(fail, -1, si..

알고리즘/baekjoon 2024. 8. 12. 12:27