[BOJ] 2990번: BAZA

https://www.acmicpc.net/problem/2990

database에 있는 N개의 문자열중 어느 하나와 일치하는 경우 / 그렇지 않은 경우를 나눠서 생각해봅시다. 우선 그렇지 않은 경우는 전체에 대해 Trie를 만들어둔 후, 각 node에다가 visit 변수를 하나 두어 constructing 과정에서 해당 node에 방문한 횟수를 저장합니다. 방문할 때 마다 1 증가시키면 됩니다. 그리고 찾고 싶은 문자열에 대해 Trie를 따라 쭉 진행하면서 방문한 node의 visit 값을 다 더하고 추가로 N을 더해주면 됩니다.

어느 하나와 일치하는 경우에는 해당 문자열까지만으로 만든 Trie에서 위와 마찬가지 과정을 하면 되는데, 이를 맨 처음에 Trie를 construct할 때 같이 처리해줍니다. 한 문자열을 처리할 때 단순히 trie에 새로운 node를 만들고 visit 변수를 증감해주는 것에서 끝내지 않고, visit의 합을 계산해두면 됩니다.

맨 처음에는 Trie class를 만들고 26개의 자식을 두었는데 메모리초과가 떠서 자식을 vector로 관리하도록 변경했습니다. 메모리초과가 뜰 수가 없다고 생각했는데, 지금 돌이켜보니 아마 BOJ가 64비트라 포인터가 8바이트를 차지해서 최대 3만*30*(8*26+8)byte가 되어 메모리초과가 뜬 것 같네요.

https://github.com/blisstoner/BOJ/blob/master/2990.cpp