http://codeforces.com/contest/452/problem/E
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3805
再推荐两道类似的题
解法都是 并查集 + 后缀数组
想法
其实用后缀树来做这题很轻松，只不过空间比较卡。
但我们可以借助于后缀树的思想用后缀数组来实现。
后缀树其实就是后缀字典树的压缩版而已，在考虑问题的时候完全可以用后缀字典树来想，很多问题就会变得非常简单，
比如这道题，以前是用单调栈来做的，不容易想啊，

现在假想我们已经建立好一颗后缀字典树，
那么答案就是字典树中所有深度大于等于k的节点的子树中两种叶子的数量相乘的和。两种叶子指的是两种后缀。
实现
我们建立后缀数组后，想象一下这样的结构，按照height数组划分区间，
一段区间被一个最小的height统治，然后两个子区间的最小的height又分别统治着两个子区间。
然后从大到小考虑height。如果长度为k的公共子串的数量是cnt，那么这个答案肯定也会加到k-1里面去。
我们对于height相同的所有的后缀一起考虑，其实就是后缀排序之后一段段连续的后缀，这些后缀的lcp是height。
将这些连续的后缀合并起来，答案会加上两种后缀的乘积。
写的时候可以写成两个后缀集合的合并，注意去重即可。
比如下面的例子
1：111111
2：111
3：11111
4：11
5：1111111
6：111
7：1111111
1 2 3后缀， 5 6 7后缀先各自合并，然后考虑到heigth为2时，肯定是
1~3后缀中的第一种后缀 * 5~7后缀中的第二种后缀 + 
1~3后缀中的第二种后缀 * 5~7后缀中的第一种后缀
（只是描述个大概，能意会这种结构就能做了
代码也贴上来
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>
#include <vector>
#define wuyiqi
const int MOD = 1000000007;
const int N = 200610;
int sa[N],X[N],Y[N],b[N],a[N],h[N],r[N];
bool comp(int *r,int a,int b,int le)
{
		return r[a] == r[b] && r[a+le] == r[b+le];
}
void sort(int *Rank,int *Id,int n,int m)
{
		std::fill(b,b+m,0);
		for(int i = n-1; i >= 0; i--) b[Rank[i]]++;
		for(int i = 1; i < m; i++) b[i] += b[i-1];
		for(int i = n-1; i >= 0; i--) sa[--b[Rank[Id[i]]]] = Id[i];
}
void calh(int n)
{
		for(int i = 1; i <= n; i++) r[sa[i]] = i;
		int height = 0;
		for(int i = 0; i < n; i++){
				if(height) height--;
				int j = sa[r[i]-1];
				while(a[j+height]==a[i+height]) height++;
				h[r[i]] = height;
		}
}
void suffix(int n,int m=500)
{
		int *Rank = X, *Id = Y, p = 1;
		for(int i = 0; i < n; i++) Rank[i] = a[i], Id[i] = i;
		sort(Rank,Id,n,m);
		for(int j = 1; p < n; j <<= 1){
				p = 0;
				for(int i = n-j; i < n; i++) Id[p++] = i;
				for(int i = 0; i < n; i++) if(sa[i] >= j) Id[p++] = sa[i] - j;
				sort(Rank,Id,n,p);
				std::swap(Rank,Id);
				Rank[sa[0]] = 0, p = 1;
				for(int i = 1; i < n; i++)
						Rank[sa[i]] = comp(Id,sa[i-1],sa[i],j) ? p-1 : p++;
				m = p;
		}
		calh(n-1);
}
char s[N];
std::vector<std::pair<int, int> > g[N];
int fa[N], cnt[N][2];
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main()
{
    int k;
    while(scanf("%d", &k), k) {
        int n = 0;
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < 2; i++){
            scanf("%s", s);
            for(int j = 0; s[j]; j++) {
                a[n++] = s[j];
                cnt[n - 1][i] = 1;
            }
            if(!i) a[n++] = '$';
            else a[n] = 0;
        }
        for(int i = 0; i <= n; i++) fa[i]=i,g[i].clear();
        suffix(n + 1);
        h[n + 1] = 0;
        for(int i = 2; i <= n; i++) {
            g[h[i]].push_back(std::make_pair(sa[i], sa[i - 1]));
        }
        long long ret = 0, ans = 0;
        for(int i = n; i >= k; i--) {
            int sz = g[i].size();
            for(int j = 0; j < sz; j++) {
                int suf_1 = g[i][j].first;
                int suf_2 = g[i][j].second;
                int rx = find(suf_1);
                int ry = find(suf_2);
                ret -= 1LL * cnt[rx][0] * cnt[rx][1];
                ret -= 1LL * cnt[ry][0] * cnt[ry][1];
                fa[ry] = rx;
                cnt[rx][0] += cnt[ry][0];
                cnt[rx][1] += cnt[ry][1];
                ret += 1LL * cnt[rx][0] * cnt[rx][1];
            }
            ans += ret;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

• 歧哥好用功。 (0) yygy 2014-10-18 08:20:18