POJ-1743 Musial Theme(后缀数组 + 二分)(男人八题)

标签：vector   amp   前缀   cstring   init   struct   ems   scanf   男人八题   

题意:有N(1

分析:首先这个重复子串的长度至少为5，因此在最后处理结果的时候要注意。"转调"我们可以利用差分来处理，如果有两段的差值都相同的话，那么就存在两段的主题是相同的。然后我们可以利用后缀数组的高度数组求解这两个重复子串的最大长度，我们可以二分最大长度，然后检测这个最大长度是否存在，对于高度数组来说，高度数组表示以字典序排序的后缀字符串的最长公共前缀，我们只需要比较连续的一组中最小的字符串开头位置和最大的字符串开头位置，然后求解这两个差值是否大于我们的二分长度即可。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 20005;
const int inf = 0x3f3f3f3f;
int a[N];
int p[N];
int n, k;
int rk[N], tmp[N];
int sa[N], lcp[N];

bool compare_sa(int i, int j)
{
	if (rk[i] != rk[j]) return rk[i]  0) --h;
		for (; j + h = mid)
		{
			mx = max(mx, max(sa[i], sa[i + 1]));
			mn = min(mn, min(sa[i], sa[i + 1]));
			if (mx - mn >= mid) return true;
		}
		else
		{
			mx = -inf;
			mn = inf;
		}
	}
	return false;
}

void init()
{
	memset(sa, 0, sizeof sa);
	memset(lcp, 0, sizeof lcp);
	memset(rk, 0, sizeof rk);
	memset(tmp, 0, sizeof tmp);
	memset(p, 0, sizeof p);
}

int main()
{	

	while (scanf("%d", &n) != EOF, n)
	{
		init();
		for (int i = 0; i > 1;
		while (l > 1;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		if(l >= 4)
			printf("%d\n", l + 1);
		else
		{
			puts("0");
		}
	}
	
	return 0;
}

POJ-1743 Musial Theme(后缀数组 + 二分)(男人八题)

标签：vector   amp   前缀   cstring   init   struct   ems   scanf   男人八题   

原文地址：https://www.cnblogs.com/pixel-Teee/p/13359955.html