suffix automata

#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;
                    dp[cnt] = dp[now] + 1;

                    for (int j = 0; j < 26; j++)
                        if (au[nxt].to[j])
                            au[cnt].to[j] = au[nxt].to[j];

                    while (now) {
                        now = au[now].suf;
                        if (au[now].to[sym] == nxt)
                            au[now].to[sym] = cnt;
                    }
                }

                break;
            }
            else {
                au[now].to[sym] = new_end;
                dp[new_end] = max(dp[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);

    return 0;
}