Description
A substring of a string T is defined as:
T(i, k)=TT...T, 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 = {(i, j, k) | k≥K, 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| ≤ 10
1 ≤ K ≤ min{|A|, |B|}
Characters of A and B are all Latin letters.
Output
For each case, output an integer |S|.
题目大意：给两个字符串，问有多少个长度大于等于K的公共子串。
思路：首先，把两个字符串用一个未出现过的字符（如'$'）连起来，求后缀数组和height[]数组。
用每个后缀的所有前缀代表一个字符串的所有子串。
然后，按height[]的顺序从前往后扫描。
遇到第一个字符串的，就压入栈中。遇到第二个字符串的，就计算栈中与第二个字符串的长度大于等于K的公共前缀。
对于栈中每一个height[]，它与当前第二个字符串的长度大于等于K的公共前缀一共有height[]-k+1个。
sum{height[]-k+1}可以在压栈的同时统计。
用一个单调栈维护，让每个height[]只入栈和出栈一次。
最后rank小的第一个字符串和rank大的第二个字符串的长度大于等于K的公共前缀就统计出来了，统计复杂度为O(n)。
此时两个字符串反过来再做一遍即可。
代码（1469MS）：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long LL; const int MAXN = ; char s[MAXN];
int sa[MAXN], rank[MAXN], height[MAXN], c[MAXN], tmp[MAXN];
int n, apart, k; void makesa(int m) {
memset(c, , m * sizeof(int));
for(int i = ; i < n; ++i) ++c[rank[i] = s[i]];
for(int i = ; i < m; ++i) c[i] += c[i - ];
for(int i = ; i < n; ++i) sa[--c[rank[i]]] = i;
for(int k = ; k < n; k <<= ) {
for(int i = ; i < n; ++i) {
int j = sa[i] - k;
if(j < ) j += n;
tmp[c[rank[j]]++] = j;
}
int j = c[] = sa[tmp[]] = ;
for(int i = ; i < n; ++i) {
if(rank[tmp[i]] != rank[tmp[i - ]] || rank[tmp[i] + k] != rank[tmp[i - ] + k])
c[++j] = i;
sa[tmp[i]] = j;
}
memcpy(rank, sa, n * sizeof(int));
memcpy(sa, tmp, n * sizeof(int));
}
} void calheight() {
for(int i = , k = ; i < n; height[rank[i++]] = k) {
k -= (k > );
int j = sa[rank[i] - ];
while(s[i + k] == s[j + k]) ++k;
}
} struct Node {
int height, cnt;
Node(int height = , int cnt = ): height(height), cnt(cnt) {}
}; LL solve() {
LL ans = , sum = ;
stack<Node> stk; for(int i = ; i < n; ++i) {
int cnt = ;
while(!stk.empty() && stk.top().height >= height[i]) {
Node t = stk.top(); stk.pop();
cnt += t.cnt;
sum -= t.cnt * (t.height - k + 1LL);
}
if(height[i] >= k) {
cnt += (sa[i - ] < apart);
if(cnt) stk.push(Node(height[i], cnt));
sum += cnt * (height[i] - k + 1LL);
}
if(sa[i] > apart) ans += sum;
} while(!stk.empty()) stk.pop();
sum = ; for(int i = ; i < n; ++i) {
int cnt = ;
while(!stk.empty() && stk.top().height >= height[i]) {
Node t = stk.top(); stk.pop();
cnt += t.cnt;
sum -= t.cnt * (t.height - k + 1LL);
}
if(height[i] >= k) {
cnt += (sa[i - ] > apart);
stk.push(Node(height[i], cnt));
sum += cnt * (height[i] - k + 1LL);
}
if(sa[i] < apart) ans += sum;
} return ans;
} int main() {
while(scanf("%d", &k) != EOF && k) {
scanf("%s", s);
apart = strlen(s);
s[apart] = '$';
scanf("%s", s + apart + );
n = strlen(s) + ;
makesa();
calheight();
cout<<solve()<<endl;
}
}