SPOJ NSUBSTR Substrings 后缀自动机

人生第一道后缀自动机，总是值得纪念的嘛。。

后缀自动机学了很久很久，先是看CJL的论文，看懂了很多概念，关于right集，关于pre,关于自动机的术语，关于为什么它是线性的结点，线性的连边。许多铺垫的理论似懂非懂。然后看了下自动机的构造发现代码倒是挺简单，但是理解原理却是十分的困难，最后在网上找到一篇带例子的讲解帖子，我感觉算是能够说服我的吧放个链接：

http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html

本题也是CLJ论文里的题，关键是如何求right集的大小，这里的求right集的大小我给个个人的理解，首先是按拓扑序吧，那三行for就有点像基数排序的姿势了，然后再由val大的算val小的。一开始令right++,是沿着root往下走的right 的初始大小，然后再按拓扑序往pre上加，就可以统计出每个状态的right集的大小了，姿势大致如此吧，代码完全参考了CLJ的论文和下面的这个链接：

http://blog.csdn.net/acm_cxlove/article/details/8222728

很感谢各位大神的分享，让我能够对后缀自动机有更深入的理解。

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#define maxn 250050

using namespace std;

struct State{

	State *suf, *go[26];

	int val, right;

	State() :suf(0), val(0){

		memset(go, 0, sizeof(go));

	}

}*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;

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

int n;

int tot;

int dp[maxn + 50];

int cnt[maxn + 50];

State *b[2 * maxn];

int main()

{

	while (~scanf("%s", str))

	{

		init();

		n = strlen(str);

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

			extend(str[i] - 'a');

		}

		tot = cur - statePool;

		memset(cnt, 0, sizeof(cnt));

		for (int i = 0; i < tot; i++) cnt[statePool[i].val]++;

		for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];

		for (int i = 0; i < tot; i++) b[--cnt[statePool[i].val]] = &statePool[i];

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

			root = root->go[str[i] - 'a']; root->right++;

		}

		memset(dp, 0, sizeof(dp));

		for (int i = tot - 1; i > 0; i--){

			dp[b[i]->val] = max(dp[b[i]->val], b[i]->right);

			if (b[i]->suf) b[i]->suf->right += b[i]->right;

		}

		for (int i = n - 1; i >= 1; i--) dp[i] = max(dp[i], dp[i + 1]);

		for (int i = 1; i <= n; i++) printf("%d\n", dp[i]);

	}

	return 0;

}

巴特西

SPOJ NSUBSTR Substrings 后缀自动机

最新文章

热门文章