题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

打卡 打卡

时间复杂度

参考文献

Java 代码

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
    static class HashStringTemplate {
        static int base = 131;

        String line = "";
        int[] h;
        int[] p;

        public HashStringTemplate(String line) {
            this.line = line;
            onConstructor();
        }

        /**
         * 构造 hash tables
         */
        void onConstructor() {
            h = new int[line.length() + 1];
            p = new int[line.length() + 1];
            int n = line.length();
            p[0]=1;
            for (int i = 1; i <= n; i++) {
                h[i] = h[i - 1] * base + line.charAt(i - 1) - 'a' + 1;
                p[i] = p[i - 1] * base;
            }
        }

        public long getInternalHashVal(int l, int r) {
            return h[r] - h[l - 1] * p[r - l + 1];
        }
    }
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        HashStringTemplate template = new HashStringTemplate(sc.next());
        int m = sc.nextInt();
        while (m-- > 0) {
            int l1 = sc.nextInt();
            int r1 = sc.nextInt();
            int l2 = sc.nextInt();
            int r2 = sc.nextInt();
            System.out.println(template.getInternalHashVal(l1,r1) == template.getInternalHashVal(l2,r2)?"Yes":"No");
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla