#1 超时求助
查看原帖
#1 超时求助
993266
Mjunw楼主2023/5/2 17:10
package trie;

import java.io.*;
import java.util.*;

public class Code02_ACAutomation {
    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;

        // 标准 IO
        public Kattio() {
            this(System.in, System.out);
        }

        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }

        // 文件 IO
        public Kattio(String input, String output) throws IOException {
            super(output);
            r = new BufferedReader(new FileReader(input));
        }

        // 在没有其他输入时返回 null
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) {
            }
            return null;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    static class ArrayTrie {
        static class Node {
            public Node[] path = new Node[26];
            public Node fail = null;
            public boolean used = false;
            public String s = null;
            public int end = 0;

            public Node() {
                N++;
            }
        }

        public static int N = 0;
        public Node root = new Node();

        public void insert(String s) {
            if (s == null) return;

            Node node = root;
            char[] chars = s.toCharArray();
            for (int index = 0; index < chars.length; index++) {
                int pos = chars[index] - 'a';
                if (node.path[pos] == null) node.path[pos] = new Node();
                node = node.path[pos];
            }
            node.s = s;
            node.end++;
        }

        public void build() {
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                Node parent = queue.poll();
                for (int pos = 0; pos < 26; pos++) {
                    Node child = parent.path[pos];
                    if (child != null) {
                        child.fail = root;
                        Node parentFail = parent.fail;
                        while (parentFail != null) {
                            if (parentFail.path[pos] != null) {
                                child.fail = parentFail.path[pos];
                                break;
                            }
                            parentFail = parentFail.fail;
                        }
                        queue.add(child);
                    }
                }
            }
        }

        public List<String> containWords(String content) {
            ArrayList<String> ans = new ArrayList<>();
            if (content == null) return ans;

            Node node = root;
            char[] chars = content.toCharArray();
            for (int index = 0; index < chars.length; index++) {
                int pos = chars[index] - 'a';
                while (node.path[pos] == null && node != root) {
                    node = node.fail;
                }

                node = node.path[pos] == null ? root : node.path[pos];
                Node tmp = node;
                while (tmp != root) {
                    if (tmp.used) break;
                    if (tmp.s != null) {
                        ans.add(tmp.s);
                        tmp.used = true;
                    }
                    tmp = tmp.fail;
                }
            }
            return ans;
        }

        public void fastBuild() {
            Node[] queue = new Node[N];
            int start, end = start = 0;
            queue[end++] = root;
            while (start != end) {
                Node parent = queue[start++];
                for (int pos = 0; pos < 26; pos++) {
                    Node child = parent.path[pos];
                    if (child != null) {
                        child.fail = root;
                        Node parentFail = parent.fail;
                        while (parentFail != null) {
                            if (parentFail.path[pos] != null) {
                                child.fail = parentFail.path[pos];
                                break;
                            }
                            parentFail = parentFail.fail;
                        }
                        queue[end++] = child;
                    }
                }
            }
        }

        public int containWordsCount(String content) {
            int ans = 0;
            if (content == null) return ans;

            Node node = root;
            char[] chars = content.toCharArray();
            for (int index = 0; index < chars.length; index++) {
                int pos = chars[index] - 'a';
                while (node.path[pos] == null && node != root) {
                    node = node.fail;
                }

                node = node.path[pos] == null ? root : node.path[pos];
                Node tmp = node;
                while (tmp != root) {
                    if (tmp.used) break;
                    if (tmp.s != null) {
                        ans += tmp.end;
                        tmp.used = true;
                    }
                    tmp = tmp.fail;
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Kattio kattio = new Kattio();
        int n = kattio.nextInt();
        ArrayTrie ac = new ArrayTrie();
        for (int index = 0; index < n; index++) {
            ac.insert(kattio.next());
        }
        ac.fastBuild();
        kattio.println(ac.containWordsCount(kattio.next()));
        kattio.flush();
        kattio.close();
    }
}

2023/5/2 17:10
加载中...