2015
05-23

# 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

1 读取一个字符串str2并加到当前串str后；
2 读取一个整数len，问所有长度为len的子串和长度不超过len的后缀子串中，最小字典序的子串的起始下标是什么，下标从1开始计算。
3 读取一个整数len，删除当前字符串str的后len个字符。

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