2

aababaa

abaabaa

1

xx

xx

0

题意：求长度不小于 k 的公共子串的个数。

思路：还是论文上的题目。基本思路是计算 A 的所有后缀和 B 的所有后缀之间的最长公共前缀的长度。把最长公共前缀长度不小于 k 的部分所有加起来。先将两个字符串连起来，中间用一个没有出现过的字符隔开。按 height 值分组后，接下来的工作便是高速的统计每组中后缀之间的最长公共前缀之和。扫描一遍，每遇到一个 B 的后缀就统计与前面的 A 的后缀能产生多少个长度不小于 k 的公共子串，这里 A 的后缀须要用一个单调的栈来高效的维护。然后对 A 也这样做一次。

比較难理解的是单调栈这部分。还是通过举例来说吧，如果当前的height[]数组按排名的顺序依次是：1，2，3.如果这些都大于等于k值，且sa[0],sa[1],sa[2]都是B串的，当sa[3]是A串的时候，由于它和sa[2]的最长公共前缀是3，所以能够包括住前3个B串，所以能够所有累加起来；可是如果是小于等于的话，比如是1的话，那么2和3的值就须要又一次计算了，由于此时的最长公共前缀是1了，我们还须要一个num[]数组来记录此时大于等于栈顶的值的个数，由于这在之后如果有更小的时候。还须要把这些大于等于的再减掉。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

typedef long long ll;

using namespace std;

const int maxn = 200010;

int sa[maxn];

int t1[maxn], t2[maxn], c[maxn];

int rank[maxn], height[maxn];

void build_sa(int s[], int n, int m) {

    int i, j, p, *x = t1, *y = t2;

    for (i = 0; i < m; i++) c[i] = 0;

    for (i = 0; i < n; i++) c[x[i] = s[i]]++;

    for (i = 1; i < m; i++) c[i] += c[i-1];

    for (i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

    for (j = 1; j <= n; j <<= 1) {

        p = 0;

        for (i = n-j; i < n; i++) y[p++] = i;

        for (i = 0; i < n; i++)

            if (sa[i] >= j)

                y[p++] = sa[i] - j;

        for (i = 0; i < m; i++) c[i] = 0;

        for (i = 0; i < n; i++) c[x[y[i]]]++;

        for (i = 1; i < m; i++) c[i] += c[i-1];

        for (i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];

        swap(x, y);

        p = 1, x[sa[0]] = 0;

        for (i = 1; i < n; i++)

            x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ?

p-1 : p++;

        if (p >= n) break;

        m = p;

    }

}

void getHeight(int s[],int n) {

    int i, j, k = 0;

    for (i = 0; i <= n; i++)

        rank[sa[i]] = i;

    for (i = 0; i < n; i++) {

        if (k) k--;

        j = sa[rank[i]-1];

        while (s[i+k] == s[j+k]) k++;

        height[rank[i]] = k;

    }

}

int r[maxn];

int st[maxn], num[maxn];

char str1[maxn], str2[maxn];

int k, len1, len2;

ll solve(int n, int k) {

    ll i, j, tp, ans = 0;

    ll tot, top;

    for (i = 1; i <= n; i++) {

        if (height[i] < k) tot = top = 0;

        else {

            tp = 0;

            if (sa[i-1] > len1) {

                tp = 1;

                tot += height[i] - k + 1;

            }

            while (top > 0 && st[top] >= height[i]) {

                tot -= num[top] * (st[top] - height[i]);

                tp += num[top];

                top--;

            }

            st[++top] = height[i];

            num[top] = tp;

            if (sa[i] < len1)

                ans += tot;

        }

    }

    for (i = 1; i <= n; i++) {

        if (height[i] < k) tot = top = 0;

        else {

            tp = 0;

            if (sa[i-1] < len1) {

                tp = 1;

                tot += height[i] - k + 1;

            }

            while (top > 0 && st[top] >= height[i]) {

                tot -= num[top] * (st[top] - height[i]);

                tp += num[top];

                top--;

            }

            st[++top] = height[i];

            num[top] = tp;

            if (sa[i] > len1)

                ans += tot;

        }

    }

    return ans;

}

int main() {

    int i, j;

    while (scanf("%d", &k) != EOF && k) {

        scanf("%s%s",str1,str2);

        for (i = 0; str1[i]; ++i)

            r[i] = str1[i];

        r[i] = '$',len1 = i,i++;

        for (j = 0; str2[j];j++)

            r[i+j] = str2[j];

        r[i+j] = 0;

        int len = i + j; 

        build_sa(r, len+1, 128);

        getHeight(r, len);

        printf("%lld\n", solve(len, k));

    }

    return 0;

}