SPOJ LCS2 后缀自动机

多串的LCS,注意要利用拓扑序更新suf的len。

我用min,max,三目会超时，所以都改成了if,else

#pragma warning(disable:4996)
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#define maxn 100050
using namespace std;

struct State{
	State *suf, *go[26];
	int val, len[2];
	State() :suf(0), val(0){
		memset(go, 0, sizeof(go));
		memset(len, 0, sizeof(len));
	}
}*root, *last;

State statePool[maxn * 2], *cur;

void init()
{
	cur = statePool;
	root = last = cur++;
}

void extend(int w)
{
	State *p = last, *np = cur++;
	np->val = p->val + 1;
	np->len[1] = np->val;
	while (p&&!p->go[w]) p->go[w] = np, p = p->suf;
	if (!p) np->suf = root;
	else{
		State *q = p->go[w];
		if (p->val + 1 == q->val){
			np->suf = q;
		}
		else{
			State *nq = cur++;
			memcpy(nq->go, q->go, sizeof q->go);
			nq->val = p->val + 1;
			nq->len[1] = nq->val;
			nq->suf = q->suf;
			q->suf = nq;
			np->suf = nq;
			while (p&&p->go[w] == q){
				p->go[w] = nq, p = p->suf;
			}
		}
	}
	last = np;
}

char str[maxn];
int n;

int bcnt[maxn];
State *b[maxn * 2];

int main()
{
	n = 0;
	scanf("%s", str);
	init();
	int len = strlen(str);
	for (int i = 0; i < len; i++){
		extend(str[i] - 'a');
	}
	int tot = cur - root;
	memset(bcnt, 0, sizeof(bcnt));
	for (int i = 0; i < tot; i++) bcnt[statePool[i].val]++;
	for (int i = 1; i <= len; i++) bcnt[i] += bcnt[i - 1];
	for (int i = tot - 1; i >= 0; i--) b[--bcnt[statePool[i].val]] = &statePool[i];
	while (scanf("%s", str) != EOF){
		int lenb = strlen(str);
		int cnt = 0;
		State *p = root;
		for (int i = 0; i < lenb; i++){
			if (p->go[str[i] - 'a']){
				cnt++;
				p = p->go[str[i] - 'a'];
			}
			else{
				while (p&&!p->go[str[i] - 'a']) p = p->suf;
				if (!p) {
					p = root;
					cnt = 0;
				}
				else{
					cnt = p->val + 1;
					p = p->go[str[i] - 'a'];
				}
			}
			if (cnt > p->len[0]){
				p->len[0] = cnt;
			}
		}
		for (int i = tot - 1; i >= 0; i--){
			if (b[i]->len[0]<b[i]->len[1]) b[i]->len[1] = b[i]->len[0];
			if (b[i]->suf&&b[i]->suf->len[0]< b[i]->len[0]){
				b[i]->suf->len[0] = b[i]->len[0];
			}
			b[i]->len[0] = 0;
		}
	}
	int ans = 0;
	for (int i = 0; i < tot; i++){
		if (ans < b[i]->len[1]){
			ans = b[i]->len[1];
		}
	}
	printf("%d
", ans);
	return 0;
}