POJ 3518 (后缀自动机)

POJ 3518 Boring

Problem : 给一个串S，询问串S有多个子串出现至少两次且位置不重叠。

Solution : 对S串建立后缀自动机，再建立后缀树，dfs一遍统计处每个结点的子树中最长节点max和最短节点min。枚举一遍后缀自动机的节点，那么对于其对应后缀的长度要求为小于等于max - min。

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 1000008;

const int INF = 2000000008;

struct edge

{

	int u, v, nt;

};

struct suffix_automanon

{

	int nt[N][26], fail[N], a[N], qmin[N], qmax[N];

	int tot, last, root;

	int lt[N], sum;

	int p, q, np, nq;

	edge eg[N << 1];

	void add(int u, int v)

	{

		eg[++sum] = (edge){u, v, lt[u]}; lt[u] = sum;

	}

	int newnode(int len)

	{

		for (int i = 0; i < 26; ++i) nt[tot][i] = -1;

		fail[tot] = -1; a[tot] = len; qmax[tot] = 0; qmin[tot] = INF;

		lt[tot] = 0;

		return tot++;

	}

	void clear()

	{

		tot = 0;

		root = last = newnode(0);

	}

	void insert(int ch)

	{

		p = last; np = last = newnode(a[p] + 1); qmin[np] = qmax[np] = a[np];

		for (; ~p && nt[p][ch] == -1; p = fail[p]) nt[p][ch] = np;

		if (p == -1) fail[np] = root;

		else

		{

			q = nt[p][ch];

			if (a[p] + 1 == a[q]) fail[np] = q;

			else

			{

				nq = newnode(a[p] + 1);

				for (int i = 0; i < 26; ++i) nt[nq][i] = nt[q][i];

				fail[nq] = fail[q];

				fail[q] = fail[np] = nq;

				for (; ~p && nt[p][ch] == q; p = fail[p]) nt[p][ch] = nq;

			}

		}

	}

	void dfs(int u)

	{

		for (int i = lt[u]; i; i = eg[i].nt)

		{

	//		cout << u << " " << eg[i].v << endl;

			int v = eg[i].v;

			dfs(v);

			qmax[u] = max(qmax[u], qmax[v]);

			qmin[u] = min(qmin[u], qmin[v]);

		}

	}

	void solve()

	{

		long long ans = 0;

		for (int i = 1; i < tot; ++i) add(fail[i], i);

		dfs(root);

	//	for (int i = 1; i < tot; ++i) cout << qmin[i] << " " << qmax[i] << endl;

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

		{

			int len = qmax[i] - qmin[i];

			if (len > a[fail[i]]) ans += min(a[i], len) - a[fail[i]];

		}

		cout << ans << endl;

	}

}sam;

int main()

{

	string s;

	while (cin >> s)

	{

		if (s == "#") break;

		sam.clear();

		for (int i = 0, len = s.length(); i < len; ++i)

			sam.insert(s[i] - 'a');

		sam.solve();

	}

}

巴特西

POJ 3518 (后缀自动机)

POJ 3518 Boring

最新文章

热门文章