그냥 책보다 몇개 재밌다 싶었던 것들..

* Suffix tree가 수많은 애플리케이션이 있음에도 불구하고, 그간 교육에서도 소외받으면서 알고리즘의 메인스트림에 들어오지 못한것은, suffix tree에 대한 논문이 당시 최고의 논문으로 꼽혔으면서 동시에 극악의 난이도로 유명했기 때문이었다.

* Longest common substring problem(두개의 문자열에서 가장 긴 common substring 찾기)에 대해 Knuth(KMP 알고리즘을 만든 세명중 한명)조차도 이 문제 자체의 lower bound가 linear 보다 크다고 예상했다. 그러나 Suffix tree를 사용해 linear time에 풀 수 있다.

* DNA Contamination(DNA 채집, 시퀀싱 중에 에러가 끼어드는 것)을 알아내기 위해서는 string search가 사용된다. 예전에 있었던, 공룡에서 정말로 DNA를 추출했다는 발표를 기억하는지? 그때 분석한 DNA는 premature at best 임이 밝혀졌다. 실제로 분석해본 결과 새나 악어와는 전혀 다른, 오히려 인간과 가까운 DNA가 너무많이 검출되었다. 즉, DNA 추출에 참여한 인간의 DNA가 오염물질로 끼어들어가고 만 것.