너와 나의 스토리

문제: https://www.acmicpc.net/problem/10538 문제 풀이: * 이 분의 풀이를 참고하여 풀었습니다. 작은 그림의 높이: q, 너비: w 큰 그림의 높이: e, 너비: r Part 1. 작은 그림 작은 그림의 행을 하나의 단어로 취급 즉 작은 그림은 q개의 단어를 가짐 각 단어를 map에 넣어 번호를 매긴다 -> 중복되면 같은 번호를 가지는 것 이때 저는 map을 구현하여 값이 저장된 위치를 단어의 번호로 사용하였습니다. map에 존재하지 않는 단어이다 -> trie에 insert -> trie 속 단어의 끝에 해당 단어의 번호를 저장해준다. (terminal=num) * map에 이미 존재하는 단어를 넣어봐야 중복되서 의미 없음 Part 2. 큰 그림 큰 그림의 한 줄씩 보면..

문제: https://www.acmicpc.net/problem/9250 Ries님의 블로그와 위키백과를 통해 공부하였습니다. insert(key + 1); } }; step 2. fail 함수 만들기 (BFS) 규칙 1. 루트에서 거리가 1인 것들(즉, root->next[i])의 fail은 root로 초기화한다. 규칙 2. 루트로부터 거리가 2 이상이면, 직전 노드의 fail을 따라가면서 자신과 같은 값을 만나면 그 노드를 fail로 설정 queue q; root->fail = root; q.push(root); while (!q.empty()) { trie* cur = q.front(); q.pop(); for (int i = 0; i next..