# 描述

A substring of a string $T$ is defined as: $T(i, k)= T_iT_{i +1}…T_{i+k-1}$, $1≤ i≤ i+k-1≤|T|$.
Given two strings $A$, $B$ and one integer $K$, we define $S$, a set of triples $(i, j, k)$:$$S =\lbrace ( i, j, k)| k≥ K, A(i,k)= B(j,k)\rbrace$$
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| ≤ 10^5$
$1 ≤ K ≤ min\lbrace |A|, |B|\rbrace$
Characters of $A$ and $B$ are all Latin letters.

## Output

For each case, output an integer $|S|$.

# 思路

• 先把两个串连接起来，中间用一个没有出现的字符分开（这类题目都是这个套路）。然后求后缀数组和$height$数组。对$height$数组进行分组使得某个组内的$height$值都不小于$k$。
• 遍历一遍$height$数组，每遇到一个$A$的后缀就统计一下它前面的$B$的后缀能组成多少公共子串，同理$A$和$B$反一下再扫一遍，就得到了答案。
• 但是这个统计是$O(n^2)$的。由于两个后缀的LCP是它们的区间最小值，所以可以维护一个自底向上递增的单调栈，同时维护栈中的总和和已经在栈中每一个元素的出现次数。每一次弹出，相当于就是用较小的$height$去替换了较大的。具体的细节看代码细细体会~

0%