题目传送。做这套题目本来是冲着奖品去的 ... 结果小岛,kuangbin,cxlove之类的全来了,就不提伤心事了,这个问题也很有意思。给定两个字符串,stra、strb(1 <= len(stra), len(strb) <= 100000),以及一个正整数k(0 <= k <= 5),问stra中有多少个和strb等长的子串,使得该子串通过修改不超过k个字符可以和strb完全一样。

kmp算法可以在O(n+m)时间内对两个字符串进行匹配,可是这个题目进行的并不是精确匹配,作者遂起名为扩展-kmp?真是会忽悠人。后来看到官方题解是后缀数组,字符串算法白痴直接略过了。其实字符串相关的很多问题都可以用字符哈希+好的想法搞定。这里我们可以根据哈希值二分出两个字符串精确匹配到的最长位置,然后以当前不匹配位置为断点,对剩余字符串继续执行此操作,最后比较断点个数与k的大小,如果不超过k,那么就找到了一个答案。