【链接】h在这里写链接

【题意】

给你n个字符串。

让你找最长的字符串s;

这个s在超过一半的子串里面都有出现过且长度大于n/2;

如果有多个,输出多行。

(按字典序输出)

也没说会不会出现大写。

【题解】

后缀数组+二分。

把每个字符串之间用一个没出现过的分隔符分开;

(从'z'+1开始)

100*1000 + 100

大概10万多的样子,设置成15万就好

长度越大,肯定是越不可能出现的。

有单调性的。

l = 2,r = 1000,temp = 0;

while (l <= r)...

连续的大于等于二分的长度的Height组

看看Sa值是不是把n/2 + 1个以上的覆盖到了。

(用set就好)

注意答案为1的时候的二分;

【错的次数】

【反思】

在这了写反思

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <set>

using namespace std;

const int N = 15e4;

const int MAX_CHAR = 1000;//每个数字的最大值。

int s[N + 10];//如果是数字,就写成int s[N+10]就好,从0开始存

int Sa[N + 10], T1[N + 10], T2[N + 10], C[N + 10];

int Height[N + 10], Rank[N + 10];

void build_Sa(int n, int m) {

	int i, *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 (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 = 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] + k] == y[Sa[i] + k] ? p - 1 : p++;

		if (p >= n) break;

		m = p;

	}

}

void getHeight(int n)

{

	int i, j, k = 0;

	for (i = 1; 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;

	}

}

const int MAXL = 1000;

int n,len,idx[N+10];

char S[MAXL + 10];

bool ok(int l)

{

	//找同一组大于等于l的

	set <int> mset;

	mset.clear();

	for (int i = 2; i <= len; i++)//枚举排名第i的后缀

		if (Height[i]>=l)

		{

			mset.insert(idx[Sa[i - 1]]), mset.insert(idx[Sa[i]]);//

		}

		else

		{

			if ((int)mset.size() >= n / 2 + 1) return true;

			mset.clear();

		}

	if ((int)mset.size() >= n / 2 + 1) return true;

	return false;

}

void out(int l)

{

	set <int> mset;//模拟之前的过程再做一遍就好

	mset.clear();

	for (int i = 2; i <= len; i++)//枚举排名第i的后缀

		if (Height[i] >= l)

		{

			mset.insert(idx[Sa[i - 1]]), mset.insert(idx[Sa[i]]);//

		}

		else

		{

			if ((int)mset.size() >= n / 2 + 1)

			{

				for (int j = Sa[i - 1]; j <= Sa[i - 1] + l - 1; j++)

					putchar((char)s[j]);

				puts("");

			}

			mset.clear();

		}

	//不可能为0

}

int main() {

	//freopen("F:\\rush.txt", "r", stdin);

	while (~scanf("%d", &n) && n>0)

	{

		len = 0;int  ls;

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

		{

			scanf("%s", S);

			ls = strlen(S);

			for (int j = 0; j < ls; j++) {

				idx[len] = i;

				s[len++] = S[j];

			}

			idx[len] = i;

			s[len++] = i + 'z';

		}

		s[len] = 0;

		build_Sa(len + 1, MAX_CHAR);

		getHeight(len);

		//开始二分最后的答案的长度

		int l = 1, r = MAXL, temp = 0;

		while (l <= r)

		{

			int mid = (l + r) >> 1;

			if (ok(mid))

			{

				temp = mid;

				l = mid + 1;

			}

			else

			{

				r = mid - 1;

			}

		}

		if (temp == 0)

			puts("?");

		else

			out(temp);

		puts("");

	}

	return 0;

}

巴特西

【POJ 3294】Life Forms