Glass Beads

UVA719

将循环串SSS展开成两倍大小：S+SS+SS+S，这样线性处理就可以处理所有循环的情况了。对S+SS+SS+S建立一个后缀自动机，让后从初始状态开始走，每次选择字典序最小的道路，走NNN步就得到一个字典序最小的原串了。假设最后走到ppp，那么此时首字符下标即为len(p)−N+1len(p)-N+1len(p)−N+1，即从首字符的位置走了NNN步到ppp。

AC代码：

#include<iostream>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

#include<map>

using namespace std;

const int MAXN = 20000;

int n;

char S[2*MAXN], Buffer[MAXN];

struct SAM {

	int size, last;

	struct Node {

		int len, link;

		int next[26];

		int cnt;

		void clear() {

			len = link = 0;

			memset(next, 0, sizeof(next));

		}

	} node[MAXN * 2];

	void init() {

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

			node[i].clear();

		}

		node[0].link = -1;

		size = 1;

		last = 0;

	}

	void insert(char x) {

		int ch = x - 'a';

		int cur = size++;

		node[cur].len = node[last].len + 1;

		node[cur].cnt = 1;

		int p = last;

		while (p != -1 && !node[p].next[ch]) {

			node[p].next[ch] = cur;

			p = node[p].link;

		}

		if (p == -1) {

			node[cur].link = 0;

		}

		else {

			int q = node[p].next[ch];

			if (node[p].len + 1 == node[q].len) {

				node[cur].link = q;

			}

			else {

				int clone = size++;

				node[clone] = node[q];

				node[clone].len = node[p].len + 1;

				node[clone].cnt = 0;

				while (p != -1 && node[p].next[ch] == q) {

					node[p].next[ch] = clone;

					p = node[p].link;

				}

				node[q].link = node[cur].link = clone;

			}

		}

		last = cur;

	}

} sam;

int main() {

	int T;

	scanf("%d", &T);

	while (T--) {

		sam.init();

		scanf("%s", S);

		n = strlen(S);

		strcpy(Buffer, S);

		strcat(S, Buffer);

		n = strlen(S);

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

			sam.insert(S[i]);

		}

		int&& Cur = 0;

		n /= 2;

		//走N步

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

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

				//如果走得通（走最小的）

				if (sam.node[Cur].next[j]) {

					Cur = sam.node[Cur].next[j];

					break;

				}

			}

		}

		printf("%d\n", sam.node[Cur].len - n + 1);

	}

	return 0;

}

巴特西

Glass Beads

最新文章

热门文章