structstate { int maxlen, minlen, slink; int trans[M]; };
state st[N * 2 + 10]; int degree[N * 2 + 10]; int endpos[N * 2 + 10]; bool prefix[N * 2 + 10];
char s[N + 10]; int size, last;
intnew_state(int maxlen, int minlen, int slink, int *trans){ prefix[size] = false; degree[size] = 0; endpos[size] = 0; st[size].maxlen = maxlen; st[size].minlen = minlen; st[size].slink = slink; for (int i = 0; i < M; i++) { if (trans == NULL) st[size].trans[i] = -1; else st[size].trans[i] = trans[i]; } return size++; }
intadd_char(char ch, int u){ int c = ch - 'a', v, x, y; int cur = new_state(st[u].maxlen + 1, -1, -1, NULL); prefix[cur] = true; endpos[cur] = 1; for (v = u; v != -1 && st[v].trans[c] == -1; v = st[v].slink) { st[v].trans[c] = cur; } if (v == -1) { st[cur].minlen = 1; st[cur].slink = 0; degree[0]++; return cur; } x = st[v].trans[c]; if (st[v].maxlen + 1 == st[x].maxlen) { st[cur].minlen = st[x].maxlen + 1; st[cur].slink = x; degree[x]++; return cur; }
y = new_state(st[v].maxlen + 1, -1, st[x].slink, st[x].trans); for (int w = v; w != -1 && st[w].trans[c] == x; w = st[w].slink) st[w].trans[c] = y; st[x].slink = st[cur].slink = y; degree[y] += 2; st[x].minlen = st[cur].minlen = st[y].maxlen + 1; st[y].minlen = st[st[y].slink].maxlen + 1;
return cur; }
voidtopo(){ queue<int> q; for (int i = 1; i < size; i++) { if (degree[i] == 0) q.push(i); } while (!q.empty()){ int x = q.front(); q.pop(); endpos[st[x].slink] += endpos[x]; if (--degree[st[x].slink] == 0) q.push(st[x].slink); } }
intnew_state(int maxlen, int minlen, int slink, int *trans){ prefix[size] = false; degree[size] = 0; endpos[size] = 0; st[size].maxlen = maxlen; st[size].minlen = minlen; st[size].slink = slink; for (int i = 0; i < M; i++) { if (trans == NULL) st[size].trans[i] = -1; else st[size].trans[i] = trans[i]; } return size++; }
intadd_char(char ch, int u){ int c = ch - '0', v, x, y; int cur = new_state(st[u].maxlen + 1, -1, -1, NULL); prefix[cur] = true; endpos[cur] = 1; for (v = u; v != -1 && st[v].trans[c] == -1; v = st[v].slink) { st[v].trans[c] = cur; } if (v == -1) { st[cur].minlen = 1; st[cur].slink = 0; degree[0]++; return cur; } x = st[v].trans[c]; if (st[v].maxlen + 1 == st[x].maxlen) { st[cur].minlen = st[x].maxlen + 1; st[cur].slink = x; degree[x]++; return cur; }
y = new_state(st[v].maxlen + 1, -1, st[x].slink, st[x].trans); for (int w = v; w != -1 && st[w].trans[c] == x; w = st[w].slink) st[w].trans[c] = y; st[x].slink = st[cur].slink = y; degree[y] += 2; st[x].minlen = st[cur].minlen = st[y].maxlen + 1; st[y].minlen = st[st[y].slink].maxlen + 1;
return cur; }
voidtopo(){ queue<int> q; for (int i = 1; i < size; i++) { if (degree[i] == 0) q.push(i); } while (!q.empty()){ int x = q.front(); q.pop(); endpos[st[x].slink] += endpos[x]; if (--degree[st[x].slink] == 0) q.push(st[x].slink); } }
intnew_state(int maxlen, int minlen, int slink, int *trans){ prefix[size] = false; degree[size] = 0; endpos[size] = 0; st[size].maxlen = maxlen; st[size].minlen = minlen; st[size].slink = slink; for (int i = 0; i < M; i++) { if (trans == NULL) st[size].trans[i] = -1; else st[size].trans[i] = trans[i]; } return size++; }
intadd_char(char ch, int u){ int c = ch - 'a', v, x, y; int cur = new_state(st[u].maxlen + 1, -1, -1, NULL); prefix[cur] = true; endpos[cur] = 1; for (v = u; v != -1 && st[v].trans[c] == -1; v = st[v].slink) { st[v].trans[c] = cur; } if (v == -1) { st[cur].minlen = 1; st[cur].slink = 0; degree[0]++; return cur; } x = st[v].trans[c]; if (st[v].maxlen + 1 == st[x].maxlen) { st[cur].minlen = st[x].maxlen + 1; st[cur].slink = x; degree[x]++; return cur; }
y = new_state(st[v].maxlen + 1, -1, st[x].slink, st[x].trans); for (int w = v; w != -1 && st[w].trans[c] == x; w = st[w].slink) st[w].trans[c] = y; st[x].slink = st[cur].slink = y; degree[y] += 2; st[x].minlen = st[cur].minlen = st[y].maxlen + 1; st[y].minlen = st[st[y].slink].maxlen + 1;
return cur; }
voidtopo(){ queue<int> q; for (int i = 1; i < size; i++) { if (degree[i] == 0) q.push(i); } while (!q.empty()){ int x = q.front(); q.pop(); endpos[st[x].slink] += endpos[x]; if (--degree[st[x].slink] == 0) q.push(st[x].slink); } }