Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int N = int(1e5 + 5);
- struct node {
- int suf;
- int to[26];
- };
- node au[N];
- int end, cnt, new_end, dp[N];
- char s[N];
- int main() {
- gets(s);
- int l = strlen(s);
- for (int i = 0; i < l; i++) {
- cnt++;
- new_end = cnt;
- int sym = s[i] - 'a';
- au[end].to[sym] = new_end;
- dp[new_end] = dp[end] + 1;
- int now = end;
- while (now) {
- now = au[now].suf;
- if (au[now].to[sym]) {
- int nxt = au[now].to[sym];
- if (dp[nxt] == dp[now] + 1) {
- au[new_end].suf = nxt;
- }
- else {
- cnt++;
- au[nxt].suf = cnt;
- for (int j = 0; j < 26; j++)
- if (au[nxt].to[j]) {
- au[cnt].to[j] = au[nxt].to[j];
- dp[ au[cnt].to[j] ] = max(dp[ au[cnt].to[j] ], dp[j] + 1);
- }
- while (now) {
- now = au[now].suf;
- if (au[now].to[sym] == nxt) {
- au[now].to[sym] = cnt;
- dp[cnt] = max(dp[cnt], dp[now] + 1);
- }
- }
- }
- break;
- }
- else {
- au[now].to[sym] = new_end;
- dp[new_end] = max(dp[new_end], dp[now] + 1);
- }
- }
- end = new_end;
- for (int i = 0; i <= cnt; i++) {
- for (int j = 0; j < 26; j++)
- if (au[i].to[j]) {
- printf("edge %d-%d through %c\n", i, au[i].to[j], 'a' + j);
- }
- }
- for (int i = 0; i <= cnt; i++)
- printf("suf[%d] = %d\n", i, au[i].suf);
- puts("----------------");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement