Description

A substring of a string T is defined as:

T(i, k)=TiTi+1Ti+k-1, 1≤ii+k-1≤|T|.
Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):

S = {(i, j, k) | kK, A(i, k)=B(j, k)}.
You are to give the value of |S| for specific A, B and K.

Input

The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.

1 ≤ |A|, |B| ≤ 105
1 ≤ Kmin{|A|, |B|}
Characters of A and B are all Latin letters.

Output

For each case, output an integer |S|.

Sample Input

Sample Output

Source

单调栈+sa 思考了很久的这题
求有多少个子串分别属于A,B并且他们的lcp>=k
那么首先一个显然的想法是枚举每个后缀把他们的lcp加起来 但是这不okay 时间T飞
那考虑怎么办 要多多利用前面的信息才可以 维护一个递增的序列 只进不出 然后num1 num2分别记录的是满足当前height的情况下 我如果新来一个其他串的子串我可以和他们构成多少个子串
为什么要维护递增的 保证我修改的复杂度不会回撤太多 但是想了想也许也可以给卡死的吧 想办法构造height是递减的即可qwq不知道能否构造这样的数据 然后每次做的时候先把上一个串的影响入队 并且加到num里面 然后再做我这个串的时候判断我是第一个还是第二个串 分别加上不同的num 然后刚刚那个回撤操作其实是要把多的影响减去 因为被我当前这个height限制住了 我两个后缀的lcp是 他们之间的最小值才对 大概看代码还是可以理解的

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论