SAM的应用及例题

专门开一个帖子记录一下自己在学习SAM时做的题&＃xff0c;并总结一下做法

1、LCS https://www.cnblogs.com/wenci/p/10432932.html

这道题是要求对两个字符串查找最长公共子串&＃xff0c;具体做法就是先对一个串建SAM&＃xff0c;然后另一个串在SAM上大力匹配&＃xff0c;具体匹配策略见以上链接

2.、LCS2 https://www.cnblogs.com/wenci/p/10433227.html

既然我们会了两个串的匹配&＃xff0c;那么多个串也应该会吧(手动滑稽) 在匹配的时候维护一个当前的最大匹配maxx和之前所有的最大匹配的minn&＃xff0c;具体见链接