求助,SAM 全部 RE 本地+Luogu IDE 可过
查看原帖
求助,SAM 全部 RE 本地+Luogu IDE 可过
230933
Tony102楼主2021/8/1 20:10

rt, 在本地和洛谷 IDE 全部可以通过。但是交上去就一直 RE (已经试了读入后面开始有问题

求助,感激不尽

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef std::vector < int > vec;
const int SIZE = 2e6 + 5, SIZE_C = 55;

int n; LL ans;
char str[SIZE]; vec edge[SIZE];

namespace SAM {
    int top, lst;
    struct node {
        int to, len, cnt, nxt[SIZE_C];
    } s[SIZE];

    void init() {
        top = lst = 1;
        s[top].len = s[top].to = 0;
    }

    int add(int c) {
        int cur = ++ top, u = lst, v;
        s[cur].len = s[lst].len + 1, s[cur].cnt = 1;
        for ( ; u && !s[u].nxt[c]; u = s[u].to) s[u].nxt[c] = cur;
        if (!u) s[cur].to = 1;
        else {
            v = s[u].nxt[c];
            if (s[u].len + 1 == s[v].len) s[cur].to = v;
            else {
                int cp = ++ top;
                s[cp] = s[v], s[cp].len = s[u].len + 1, s[cp].cnt = 0;
                for ( ; u && s[u].nxt[c] == v; u = s[u].to) s[u].nxt[c] = cp;
                s[v].to = s[cur].to = cp;
            }
        }   
        lst = cur;
    }
} using namespace SAM;

void dfs(int u) {
    for (int v: edge[u]) {
        dfs(v);
        s[u].cnt += s[v].cnt;
    }
    if (s[u].cnt - 1) ans = std::max(ans, 1ll * s[u].cnt * s[u].len);
}

int main() {
    // freopen("code.in", "r", stdin);
    std::cin >> str + 1;
    n = strlen(str + 1); init();
    for (int i = 1; i <= n; ++ i) add(str[i] - 'a');
    for (int i = 2; i <= top; ++ i) edge[s[i].to].emplace_back(i);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
2021/8/1 20:10
加载中...