CF 427D Match & Catch 求最短唯一连续LCS

题目来源：CF 427D Match & Catch

题意：给出2个字符串 求最短的连续的公共字符串 而且该字符串在原串中仅仅出现一次

思路：把2个字符串合并起来求height 后缀数组height的应用

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 100010;

char s[maxn];

int sa[maxn];

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

int rank[maxn], height[maxn];

int l1, l2;

void build_sa(int m, int n)

{

	int i, *x = t, *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(int k = 1; k <= n; k <<= 1)

	{

		int p = 0;

		for(i = n-k; i < n; i++)

			y[p++] = i;

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

			if(sa[i] >= k)

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

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

			c[i] = 0;

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

			c[x[y[i]]]++;

		for(i = 0; 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]+k] == y[sa[i]+k] ?

p-1 : p++;

		if(p >= n)

			break;

		m = p;

	}

}

void getHeight(int n)

{

	int k = 0;

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

		rank[sa[i]] = i;

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

	{

		if(k)

			k--;

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

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

			k++;

		height[rank[i]] = k;

	}

}

bool ok(int m, int n)

{

	int cnt1 = 0, cnt2 = 0;

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

	{

		if(height[i] >= m)

		{

			if(sa[i-1] < l1)

				cnt1++;

			if(sa[i-1] > l1)

				cnt2++;

		}

		else

		{

			if(sa[i-1] < l1)

				cnt1++;

			if(sa[i-1] > l1)

				cnt2++;

			if(cnt1 == 1 && cnt2 == 1)

				return true;

			cnt1 = cnt2 = 0;

		}

	}

	return false;

}

int main()

{

	char a[5555], b[5555];

	while(scanf("%s %s", &a, &b) != EOF)

	{

		l1 = strlen(a);

		l2 = strlen(b);

		int n = 0;

		for(int i = 0; i < l1; i++)

			s[n++] = a[i];

		s[n++] = 'z'+1;

		for(int i = 0; i < l2; i++)

			s[n++] = b[i];

		s[n] = 0;

		build_sa(128, n+1);

		getHeight(n);

		int l = 1, r = 5000;

		int ans = -1;

		int len = min(l1, l2);

		for(int i = 1; i <= len; i++)

			if(ok(i, n))

			{

				ans = i;

				break;

			}

		if(ans <= 0)

			printf("-1\n");

		else

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

	}

	return 0;

}