PKU2019数据结构与算法实习作业 11~21

2019年12月29日1,2520

题目来源:http://dapractise.openjudge.cn/2019hwall/

多模式串字符串匹配模板题

AC自动机模板题

POJ3987 Computer Virus on Planet Pandora

躲不开的病毒

找自动机上的环

POJ3691 DNA repair

DP,考虑前 i 个字符且停留在trie树上编号为 j 的节点时,字符串所修改的最小次数

POJ3450 Corporate Identity

把所有串连接起来建后缀数组

POJ2774 Long Long Message

分隔符将两个字符串连接

后缀数组求height数组后

只要相邻两个分别在两串,就可以用height更新ans

POJ3415 Common Substrings

POJ2186 Popular Cows

如果 X 喜欢 Y,Y 向 X 连边。缩点以后,计算每个强连通块的入度,唯一的入度为 0 的块大小就是答案。

POJ2762 Going from u to v or from v to u?

缩点重建图后判断拓扑排序是否唯一

POJ1860 Currency Exchange

POJ1523 SPF

avatar
  Subscribe  
提醒