首页 > 搜索 > DFS搜索 > HDU 4270-Dynamic Lover-字符串-[解题报告]HOJ
2015
05-23

HDU 4270-Dynamic Lover-字符串-[解题报告]HOJ

Dynamic Lover

问题描述 :

As a famous person with universal love, changing girlfriend too often makes me harassment because I can’t keep their name in mind timely. To remember who is my lover now, I buy a magic password-box from a wizard.
As a faithful atheist, I do not believe that it is caused by magic power. By doing a deep research, I find that all "magic" factors are just because a small software inside the box. Because the software only uses some simple data structure, it has a dissatisfied complexity.
Now I shortly introduce the principle of the software.
We will support a string with dynamic length and three kinds of operations on it. You can assume that we will always have an initial string.
*1. You will receive a short string, and you should connect it after the original string to make the new string.
*2. You will receive an integer len, and you should answer the query: for each index i (1 <= i <= LEN(nowString)), we will get a sub-string from i to i + len – 1 (if i + len – 1 > LEN(nowString), you should make the suffix from index i as its sub-string). You should output the index i whose sub-string has minimum lexicographic.
*3. You will receive an integer len. You should delete the suffix whose length is len from the string now and get a new string.
As a former ACMer, I want to make a new production with better execution speed. But I am not good at data structure, so I need your help.

输入:

There are multiple test cases.
The first line contains a string as the initial string.
The next line contains an integer m (1 <= m <= 100,000) indicating the number of the operations.
Each of the next m lines begins with an integer k (1 <= k <= 3) indicating the kind of operation. If k = 1, it is followed by a short non-empty string, otherwise it is followed by an integer len.
We guarantee that the total length of the initial string and all short strings are not more than 100,000. And for each query, the len is not more than 1000 and the total sum of len is not more than 100,000.
All characters in the input are lower case.

输出:

There are multiple test cases.
The first line contains a string as the initial string.
The next line contains an integer m (1 <= m <= 100,000) indicating the number of the operations.
Each of the next m lines begins with an integer k (1 <= k <= 3) indicating the kind of operation. If k = 1, it is followed by a short non-empty string, otherwise it is followed by an integer len.
We guarantee that the total length of the initial string and all short strings are not more than 100,000. And for each query, the len is not more than 1000 and the total sum of len is not more than 100,000.
All characters in the input are lower case.

样例输入:

aacbab
5
2 2
1 aaa
2 3
3 2
2 3 

样例输出:

1
9
7

HDU 4270
题意:初始给一个字符串str,然后又给出三种操作:
1 读取一个字符串str2并加到当前串str后;
2 读取一个整数len,问所有长度为len的子串和长度不超过len的后缀子串中,最小字典序的子串的起始下标是什么,下标从1开始计算。
3 读取一个整数len,删除当前字符串str的后len个字符。

输入数据中的str和str2的总长度不超过哦100000,每一次询问的长度不会超过1000,并且所有询问综合的长度不会超过100000。


分析:因为后缀自动机能识别一个合法的子串,那么考虑在后缀自动机上进行深搜,从根节点开始,每次都往字典序小的字符扩展,假如搜到的当前节点x时,搜过的长度为len,或者搜到末尾节点last,节点x代表的字符在字符串str中的位置是pos,答案就是pos-len+1;有一点要注意,因为也可能会有长度小于len的后缀是字符串的子串,所以,从last的fail指针到达的节点,也是字符串str的合法后缀,所以在深搜之前,需要先标记一下这些末尾节点。
还有就是删除的操作,在构造后缀自动机的时候,会复制一些节点,表示表示不同的转移状态,那么在删除其中一个节点时,它的复制节点也应该删除,所以可以考虑在节点信息里再加一个域,表示是否删除,这个域是一个指针,复制的节点共用一个指针,删除的时候可以直接标记这个域,表示节点是否被删除。注意删除的时候更新末尾节点last。
最后就是添加字符串了,直接一个一个字符加入到后缀自动机即可。

/* HDU 4270 Dinamic Lover
 * 后缀自动机
 * */
#include <cstdio>
#include <cstring>

#define noDEBUG

const int MAXN = 200005;

struct SAMNode {
	SAMNode *f, *ch[26];
	int len;
	bool *d;
	int pos; /* 节点在字符串的位置 */
	int v;
#ifdef DEBUG
	char c;
#endif
};
SAMNode *root, *last;
int p_cnt, d_cnt, seq_len, v_id;
SAMNode pool[MAXN*2];
bool is_d[MAXN*2];
char str[MAXN];
SAMNode *seq[MAXN];

bool is_del(SAMNode *x) {
	return x == NULL || *x->d;
}

void append(char ch) {
	int c = ch - 'a';
	SAMNode *p = last, *np = pool + p_cnt++;
	memset(np, 0, sizeof(*np));
	np->pos = np->len = p->len + 1;
	np->d = is_d + d_cnt++;
	*np->d = false;
#ifdef DEBUG
	np->c = ch;
#endif
	seq[seq_len = np->len] = np;
	last = np;
	for (; NULL != p && is_del(p->ch[c]); p = p->f) p->ch[c] = np;
	if (NULL == p) {
		np->f = root;
	} else {
		if (p->ch[c]->len == p->len + 1) {
			np->f = p->ch[c];
		} else {
			SAMNode *q = p->ch[c], *nq = pool + p_cnt++;
			*nq = *q;
			nq->len = p->len + 1;
			q->f = np->f = nq;
			for (; NULL != p && p->ch[c] == q; p = p->f) p->ch[c] = nq;
		}
	}
}

void del(int len) {
	while (len--) *seq[seq_len--]->d = true;
	last = seq[seq_len];
}

int dfs_len;
int dfs(SAMNode *x, int l) {
#ifdef DEBUG
	if (x->c) putchar(x->c);
#endif
	if (l == dfs_len) return x->pos - l  + 1;
	if (x->v == v_id) return seq_len - l + 1;
	for (int i = 0; i < 26; ++i) {
		if (!is_del(x->ch[i])) {
			return dfs(x->ch[i], l+1);
		}
	}
	return x->len - l + 1;
}

int query(int len) {
#ifdef DEBUG
	printf("%s %d:", str, len);
#endif
	++v_id;
	for (SAMNode *p = last; p != root; p = p->f) p->v = v_id;
	dfs_len = len;
	int ret = dfs(root, 0);
#ifdef DEBUG
	printf("\n");
#endif
	return ret;
}

int main() {
	while (EOF != scanf("%s", str)) {
		root = last = pool;
		memset(root, 0, sizeof(*root));
		root->d = is_d;
		is_d[0] = false;
		p_cnt = 1;
		d_cnt = 1;
		v_id = 0;
		seq[0] = root;
		for (char *c = str; *c; ++c) append(*c);

		int m, q, len;
		scanf("%d", &m);
		while (m--) {
			scanf("%d", &q);
			if (1 == q) {
				scanf("%s", str);
				for (char *c = str; *c; ++c) append(*c);
			} else if (2 == q) {
				scanf("%d", &len);
				printf("%d\n", query(len));
			} else if (3 == q) {
				scanf("%d", &len);
				del(len);
			} else {
				for(;;);
				fprintf(stderr, "error cmd %d\n", q);
			}
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/moorage/article/details/8224921