【POJ 3415】Common Substrings 长度不小于k的公共子串的个数

时间：2021-08-06 07:41:09

长度不小于k的公共子串的个数，论文里有题解，卡了一上午，因为sum没开long long！！！

没开long long毁一生again～～～

以后应该早看POJ里的Discuss啊QAQ

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N = 200003;

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

void st(int *x, int *y, int *sa, int n, int m) {

	int i;

	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];

}

void mkhz(int *a, int *sa, int n, int m) {

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

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

	st(x, y, sa, n, m);

	for(p = 1, j = 1; p < n; j <<= 1, m = p) {

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

		for(i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

		st(x, y, sa, n, m);

		for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)

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

	}

}

void mkh(int *r, int *sa, int *rank, int *h, int n) {

	int i, j, k = 0;

	for(i = 1; i <= n; ++i) rank[sa[i]] = i;

	for(i = 1; i <= n; h[rank[i++]] = k)

		for(k ? --k : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; ++k);

}

char s[N];

int a[N], sa[N], rank[N], h[N], n, k, sta[N], top, tmp, mark[N];

long long sum[N];

int main() {

	while (scanf("%d", &k), k) {

		scanf("%s", s + 1);

		tmp = strlen(s + 1);

		s[++tmp] = 1;

		scanf("%s", s + tmp + 1);

		n = strlen(s + 1);

		for(int i = 1; i <= n; ++i) a[i] = s[i];

		mkhz(a, sa, n + 1, 130);

		mkh(a, sa, rank, h, n);

		long long ans = 0;

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

			if (h[i] < k) {

				top = sum[0] = sum[1] = 0;

			} else {

				for(int j = top; sta[j] > h[i] - k + 1 && j; --j) {

					sum[mark[j]] += h[i] - k + 1 - sta[j];

					sta[j] = h[i] - k + 1;

				}

				sta[++top] = h[i] - k + 1;

				if (sa[i - 1] < tmp) mark[top] = 0;

				if (sa[i - 1] > tmp) mark[top] = 1;

				sum[mark[top]] += h[i] - k + 1;

				if (sa[i] < tmp) ans += sum[1];

				if (sa[i] > tmp) ans += sum[0];

			}

		}

		printf("%lld\n", ans);

	}

	return 0;

}

没开long long，毁我青春，耗我钱财，颓我精神==

相关文章