【题意】
给定一个数k
在给定两个字符串A,B
求三元组(i,j,k)(表示从A的第i位起和从B的j位起长度为k的字符串相同)的个数
【输入】
多组数据
每组数据第一行为k
接下来两行分别为A、B(长度均不大于100000)
【输出】
对于每组数据,输出一个数,表示三元组的个数
后缀数组应用题之一
后缀数组的用法很经典
将两个字符串之间加一个没出现过的字符连接起来
然后求height
对于B的一个后缀,对应每一个A的后缀若他们的公共前缀长为l,若l大于等于k,则会有l-k+1种三元组
这个统计便是本题的难点
如果枚举A的后缀和B的后缀,那么复杂......
阅读全文