dlwocks31의 PS일기장

https://www.acmicpc.net/source/share/412dd80e9e794587a5a0f3b851164ff7 공유 소스 보기 www.acmicpc.net KMP로 모든 string마다 suffix와 prefix가 같은 suffix/prefix의 길이를 찾을 수 있다는 생각을 했는데, 답을 빠르게 찾는데는 큰 도움이 되지 않았다. 생각이 안나서 결국에 공식풀이를 봤는데, 매우 신기한 방법이 있었다. 이 문제에서 a가 b와 이어질려면 a가 b의 prefix이면서 suffix이여야 한다. 이 때 suffix 조건을 제거해보자. prefix만 본다면 이 문제는 trie로 어렵지 않게 풀 수 있다. 각 노드마다 (이 노드에서 끝나는 string이 있다면)이 노드의 string에서 끝나는 최적의 답..