最后四个测试点runtime error,求看看哪里出问题
查看原帖
最后四个测试点runtime error,求看看哪里出问题
1037537
_Aoi楼主2023/8/29 19:07
import java.util.*;
public class Main {
    static int M=1000001;
    static int N=1000001;
    static class Trie {
        int tot=1;
        int[] col = new int[M];
        int[] fa= new int[M];
        int[][] ch= new int[M][26];
        void insert(String s) {
            int now = 1;
            for (int i=0;i<s.length();i++) {
                int c = s.charAt(i) - 'a';
                if (ch[now][c] == 0) {
                    ch[now][c] = ++tot;
                    fa[tot] = now;
                    col[tot] = c;
                }
                now = ch[now][c];
            }
        }
    }
    static class SuffixAuto {
        int tot= 1;
        int[] pos = new int[N];
        int[] fa = new int[N];
        int[] len= new int[N];
        int[][] ch= new int[N][26];
        Queue<Integer> Q= new LinkedList<>();
        int insert(int c, int last) {
            int p = last;
            int q = ++tot;
            len[q] = len[p] + 1;
            while (p != 0 && ch[p][c] == 0) {
                ch[p][c] = q;
                p = fa[p];
            }
            if (p == 0) {
                fa[q] = 1;
            } else {
                int np = ch[p][c];
                if (len[p] + 1 == len[np]) {
                    fa[q] = np;
                } else {
                    int nq = ++tot;
                    len[nq] = len[p] + 1;
                    System.arraycopy(ch[np], 0, ch[nq], 0, 26);
                    while (p != 0 && ch[p][c] == np) {
                        ch[p][c] = nq;
                        p = fa[p];
                    }
                    fa[nq] = fa[np];
                    fa[q] = fa[np] = nq;
                }
            }
            return q;
        }
        void build(Trie T1) {
            for (int i = 0; i < 26; i++) {
                if (T1.ch[1][i] != 0) {
                    Q.add(T1.ch[1][i]);
                }
            }
            pos[1] = 1;
            while (!Q.isEmpty()) {
                int x = Q.poll();
                pos[x] = insert(T1.col[x], pos[T1.fa[x]]);
                for (int i = 0; i < 26; i++) {
                    if (T1.ch[x][i] != 0) {
                        Q.add(T1.ch[x][i]);
                    }
                }
            }
        }
        void query() {
            long ans = 0;
            for (int i = 2; i <= tot; i++) {
                ans += len[i] - len[fa[i]];
            }
            System.out.println(ans);
            System.out.print(tot);
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Trie T1 = new Trie();
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            T1.insert(s);
        }
        SuffixAuto SAM = new SuffixAuto();
        SAM.build(T1);
        SAM.query();
    }
}


2023/8/29 19:07
加载中...