AcWing 138. 【java】兔子与兔子    原题链接    简单

作者： 作者的头像   tt2767 ,  2019-12-12 23:46:48 ,  所有人可见 ,  阅读 798

0


// java 又T了😂， 本机离线跑了3s结果是对的

import java.util.*;

public class Main{
    void run(){
        String dna = jin.next();
        init(dna);

        int n = jin.nextInt();
        for (int i = 0 ; i < n ; i++){
            int l1 = jin.nextInt();
            int r1 = jin.nextInt();
            int l2 = jin.nextInt();
            int r2 = jin.nextInt();
            boolean ans = compare(l1, r1, l2, r2);
            System.out.println(ans ? "Yes" : "No");
        }
    }

    void init(String str){
        char[] value = str.toCharArray();
        power.add(1L);
        hash.add(0L);
        for (int i = 0 ; i < str.length(); i++){
            hash.add((hash.get(i) * base % mod + (long)(value[i] - 'a' + 1)) % mod);
            power.add(power.get(i) * base % mod);
        }
    }

    boolean compare(int l1, int r1, int l2, int r2){
        long h1 = hash.get(r1) - hash.get(l1-1) * power.get(r1-l1+1) % mod;
        long h2 = hash.get(r2) - hash.get(l2-1) * power.get(r2-l2+1) % mod;
        return h1 == h2;
    }

    private List<Long> power = new ArrayList<>();
    private List<Long> hash = new ArrayList<>();
    private long base = 131L;
    private long mod = Long.MAX_VALUE;
    private Scanner jin = new Scanner(System.in);
    public static void main(String[] args) throws Exception {new Main().run();}
}

1 评论

用户头像
Sonata_   2021-02-02 19:37         踩      回复

应该还是你处理的IO不太高效，建议使用BufferedReader
以下是我用Java AC的代码

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

class Main {
    static int N = 1000010;
    static long p = 131;
    static long[] ps = new long[N];
    static long[] hs = new long[N];

    public static int toInt(String s) {
        return Integer.parseInt(s);
    }

    public static long getSubHash(int i, int j) {
        return hs[j] - hs[i - 1] * ps[j - i + 1];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int n = line.length();
        hs[0] = 0;
        ps[0] = 1;
        for(int i = 1; i < n + 1; i++) {
            ps[i] = ps[i - 1] * p;
            hs[i] = hs[i - 1] * p + (line.charAt(i - 1) - 'a' + 1);
        }

        int m = toInt(br.readLine());
        for (int i = 0; i < m; i++) {
            String[] ws = br.readLine().split(" ");
            int l1 = toInt(ws[0]);
            int r1 = toInt(ws[1]);
            int l2 = toInt(ws[2]);
            int r2 = toInt(ws[3]);
            if (getSubHash(l1, r1) == getSubHash(l2, r2)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}