title: acwing之数据结构
date: 2021-01-25 19:50:40
tags:
-算法
-标签
categories: 算法
链表
单链表
idx表示前面使用到的下标点截止此下标之前，我们忽略因为删除造成的内存浪费
插入只从idx开始插，删除后可能idx之前的一些节点已经被删除，即浪费了一些内存
初始化
public static void init(){
head = -1;
idx = 0;
}
把x插到头结点后
//把k插入到头结点后
public static void add_to_head(int k){
e[idx] = k;
ne[idx] = head;
head = idx;
idx++;
}
把x插入到k节点后面
//把x插入到下标是k的节点后面
public static void add_to_k(int x,int k){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
把下标k节点后面的节点删除
//把下标是k的点后面的节点删掉
public static void remove(int k){
ne[k] = ne[ne[k]];
}
package 数据结构;
import java.io.BufferedInputStream;
import java.util.Scanner;
public class SingleLink {
private static final int N = 100010;
//分配单链表空间
private static int[]e = new int[N];
private static int[]ne = new int[N];
private static int head,idx;
public static void init(){
head = -1;
idx = 0;
}
//把k插入到头结点后
public static void add_to_head(int k){
e[idx] = k;
ne[idx] = head;
head = idx;
idx++;
}
//把x插入到下标是k的节点后面
public static void add_to_k(int x,int k){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//把下标是k的点后面的节点删掉
public static void remove(int k){
ne[k] = ne[ne[k]];
}
public static void main(String[] args) {
init();
Scanner in = new Scanner(new BufferedInputStream(System.in));
int m = in.nextInt();
while(m--!=0){
String s=in.next();
if(s.equals("H"))
{
int h = in.nextInt();
add_to_head(h);
}
else if(s.equals("D")){
int k = in.nextInt();
//注意此处是k-1，因为函数remove是删除第k个节点后面的节点，而要求删除第k个插入的节点（idx=k），所以这里写k-1
//如果删除最后一个插入的节点后面一个节点，那么操作不存在，所以不用讨论
if(k!=0)
remove(k-1);
else
head = ne[head];
}
else{
int k = in.nextInt(),x = in.nextInt();
add_to_k(x,k-1);
}
}
for(int i=head;i!=-1;i=ne[i]) System.out.print(e[i]+" ");
}
}
双链表
右边插入可以转换成左边插入，实现一个即可
模板
import java.io.*;
public class Main {
private static final int N = 100010;
private static int[] e = new int[N], l = new int[N], r = new int[N];
private static int head, tail, idx;
public static void init() {
head = 0;
tail = 1;
idx = 2;
r[0] = 1;
l[1] = 0;
}
//右侧插入一个节点
public static void addr(int k, int x) {
e[idx] = x;
//先连自己发出的线
l[idx] = k;
r[idx] = r[k];
//再连自己收到的线
//先连右边的线
l[r[k]] = idx;
r[k] = idx;
idx++;
}
public static void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
public static void main(String[] args) throws IOException {
init();
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = in.readLine().split(" ");
int M = Integer.parseInt(s1[0]);
while (M-- != 0) {
String[] s2 = in.readLine().split(" ");
//操作字符串
String m = s2[0];
if (m.equals("L")) {
int a = Integer.parseInt(s2[1]);
addr(0, a);
} else if (m.equals("R")) {
int a = Integer.parseInt(s2[1]);
addr(l[1], a);
//这里用equals，别用==o(╯□╰)o
} else if (m.equals("D")) {
int a = Integer.parseInt(s2[1]);
//这里和单链表不一样，原因是从idx=2开始插
remove(a + 1);
} else if (m.equals("IL")) {
int a = Integer.parseInt(s2[1]);
int b = Integer.parseInt(s2[2]);
addr(l[a + 1], b);
} else if (m.equals("IR")) {
int a = Integer.parseInt(s2[1]);
int b = Integer.parseInt(s2[2]);
addr(a + 1, b);
}
}
for (int i = r[0]; i != 1; i = r[i]) {
out.write(e[i]+" ");
out.flush();
}
in.close();
out.close();
}
}
邻接表
一堆单链表
栈和队列
单调栈
代码1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final int N = 100010;
private static int a[] = new int[N],b[] = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = in.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
String[] s2 = in.readLine().split(" ");
for(int i=1;i<=n;i++) a[i]=Integer.parseInt(s2[i-1]);
int tt = 0,i=1;
while(i<=n) {
while(tt==0||a[i]>b[tt]) {
if (i <= n)
{
if(tt==0) System.out.print(-1+" ");
else System.out.print(b[tt]+" ");
b[++tt] = a[i++];
}
if(i>n) {
return;
}
}
while(tt!=0&&a[i]<=b[tt]) {
tt--;
}
if(tt!=0) System.out.print(b[tt]+" ");
else System.out.print(-1+" ");
b[++tt]=a[i++];
}
}
}
代码
import java.io.*;
public class Main {
private static final int N = 100010;
private static int[] stk = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = in.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
String[] s2 = in.readLine().split(" ");
int tt=0;
for(int i=1;i<=n;i++) {
int x=Integer.parseInt(s2[i-1]);
while(tt!=0&&stk[tt]>=x)tt--;
if(tt==0)out.write(-1+" ");
else out.write(stk[tt]+" ");
//最后别忘了把元素放进去
stk[++tt]=x;
}
out.flush();
in.close();
out.close();
}
}
单调队列
模板
package acwing基础算法;
import java.io.*;
/**
* 优先队列模板
* 其实是用单调队列模拟单调栈
* 如果移出那么就更换队头索引
* 否则就在队尾弹栈，直至单调为止
* 注意，按照从小到大单调每次只能确定对头的最小值
* 从大到小每次只能确定对头的最大值
*/
public class SlidingWindow {
private static final int N = 1000010;
private static int[] a = new int[N], q = new int[N];
public static void main(String[] args)throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = in.readLine().split(" ");
int n = Integer.parseInt(s1[0]), k = Integer.parseInt(s1[1]);
String[] s2 = in.readLine().split(" ");
for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s2[i-1]);
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++) {
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] >= a[i]) tt--;
//要先放进去数字，可能后面放入的数无限小，弹出所有数，所以它是最小数
q[++tt] = i;
if (i - k + 1 > 0) out.write(a[q[hh]]+" ");
}
out.write("\n");
hh = 0; tt = -1;
for (int i = 1; i <= n; i++) {
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if (i - k + 1 > 0) out.write(a[q[hh]]+" ");
}
out.flush();
}
}
KMP算法
算法思想
关键就是理解next[i]数组
假设一次匹配是s[i-1]和和p[j]匹配成功，s[i]和p[j+1]不匹配，那么j=next[j]向后移动,再判断s[i]和p[j+1]是否匹配
如果匹配则退出循环再判断下一个坐标，i调至下一个。
双指针的结果是要么匹配完全，要么退回至j=0;匹配失败；
如果匹配失败j从0开始判断，i跳至下一个。
即下次匹配可以不用从p[1]开始匹配，直接从下次直接从next[i]=j开始，接着开始匹配
KMP的关键是双指针相对移动，对于每个i看是否有j+1以及next[j]更新的j的j+1能否匹配，
如果都没有，那么j从0开始，否则更新i和j，接着往下求它的子问题
注意下标从0开始和从1开始的两种不同写法
本模板采用从0开始，从1开始参考下面网站
https://www.acwing.com/activity/content/code/content/43108/
模板
import java.io.*;
/**
* 核心算法是
* 1.求next数组
* 2.根据next数组kmp匹配
*/
public class Main {
private static final int N = 100010;
private static int ne[] = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = in.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
String[] s2 = in.readLine().split(" ");
char[] p = s2[0].toCharArray();
String[] s3 = in.readLine().split(" ");
int m = Integer.parseInt(s3[0]);
String[] s4 = in.readLine().split(" ");
char[] s = s4[0].toCharArray();
//求next数组
ne[0] = -1;
for (int i = 1, j = -1; i < n; i++) {
while (j != -1 && p[i] != p[j+1]) j = ne[j];
if (p[i] == p[j+1]) j++;
ne[i] = j;
}
//kmp匹配过程
for (int i = 0, j = -1; i < m; i++) {
while (j != -1 && s[i] != p[j+1]) j = ne[j];
if (s[i] == p[j+1]) j++;
if (j == n-1) {
out.write(i - n+1+" ");
j = ne[j];
}
}
out.flush();
}
}
时间复杂度
Trie树
概念
存储
存储每个单词的字母节点，把单词的存在标记存在最后一个字母中
查找
查找单词，对于单词的每个字母，从根节点开始按子节点遍历
如果对于单词的某个字母无对应子节点出现，那么就不存在这个单词
存在所有字母，但最后一个字母不存在单词标记也不存在这个单词
用数组模拟Tire树
package 数据结构;
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Tires {
private static final int N = 100010;
private static int idx = 0;
//idx第一个插入的节点为1,0表示根节点和未被插入的节点指向的节点
private static int[][] son = new int[N][26];
private static int[] cnt = new int[N];
public static void insert(String s){
int p = 0;
for(char c:s.toCharArray()){
int u = c - ‘a‘;
if(son[p][u]==0) son[p][u]=++idx;
p = son[p][u];
}
cnt[p]++;
}
public static int query(String s){
int p = 0;
for(char c:s.toCharArray()){
int u = c - ‘a‘;
if(son[p][u]==0) return 0;
p = son[p][u];
}
return cnt[p];
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
while(n--!=0){
String s1 = in.next(),s2 = in.next();
if(s1.equals("I")){
insert(s2);
}else{
System.out.println(query(s2));
}
}
}
}
最大异或对
边插入边查找
枚举的时候注意，我们从0枚举到j=i-1，因为两个相同的数异或结果相同，所以不用重复枚举两个顺序不同的数
先插入后查找的好处是不用判断边界条件，每次都保证Tire树有可查的
package 数据结构;
import java.io.BufferedInputStream;
import java.util.Scanner;
/**
* 最大抑或对
* 1.暴力做法枚举n(n-1)/2中情况
* 2.采用Tire树优化第二层循环
*/
public class MaxXorPair {
private static final int N = 100010, M = 31 * N;
private static int[][] son = new int[M][2];
private static int idx = 0;
public static void insert(int a) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int u = a >> i & 1;
if (son[p][u] == 0) son[p][u] = ++idx;
p = son[p][u];
}
}
//根据已经插入的数，寻找a的最大异或数
//对于每个给定的数,现在只需要31步就能找到最大数并求解它的最大值，原来需要枚举到i
public static int query(int a) {
int res = 0;
int p = 0;
for (int i = 30; i >= 0; i--) {
//取出每一位
int u = a >> i & 1;
if (son[p][u ^ 1] != 0) {
//如果找得到相反的那么就去找，并且更新下一层的层数
p = son[p][u ^ 1];
res = res * 2 + (u ^ 1);
} else {
//找不到就找自己数本身的下一层
p = son[p][u];
res = res * 2 + u;
}
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
int max = 0;
for (int i = 0; i < n; i++) {
int a = in.nextInt();
//先插入再查询,查询出来最次为自己,自己异或自己为0
insert(a);
//更新max
max = Math.max(query(a) ^ a, max);
}
System.out.print(max);
}
}
并查集
概念
操作
路径压缩
时间复杂度优化为O（1）
模板
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static int find(int x){
//路径压缩，递归的调用find[父亲节点]，并且把p[x]==x时return根节点
//这样遍历的所有非根节点都连向根节点，极大的缩减了树高度，平摊下来O（1）
if(p[x]!= x) p[x] = find(p[x]);
return p[x];
}
private static final int N = 100010;
private static final int[] p = new int[N];
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt(),m = in.nextInt();
//数组下标等于p[i]就是根节点，即如果父亲节点的下标指向自己的数组下标就是根节点
for(int i = 1;i<=n;i++) p[i] = i;
while(m--!=0){
String s = in.next();
int a = in.nextInt(),b = in.nextInt();
if(s.equals("M")) p[find(a)]=find(b);
else{
if(find(a)==find(b)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}
并查集的扩展
连通块中点的数量
这道题关注的是联通块，而不是图，这道题相当于把联通块以及联通块的连接以并查集的形式（树）存储和计算了
并且维护了一个size数组
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static int find(int x) {
//路径压缩，递归的调用find[父亲节点]，并且把p[x]==x时return根节点
//这样遍历的所有非根节点都连向根节点，极大的缩减了树高度，平摊下来O（1）
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
private static final int N = 100010;
private static final int[] p = new int[N], size = new int[N];
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt(), m = in.nextInt();
//数组下标等于p[i]就是根节点，即如果父亲节点的下标指向自己的数组下标就是根节点
for (int i = 1; i <= n; i++) {
p[i] = i;
size[i] = 1;
}
while (m-- != 0) {
String s = in.next();
if (s.equals("C")) {
int a = in.nextInt(), b = in.nextInt();
if (find(a) == find(b)) continue;
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
} else if (s.equals("Q1")) {
int a = in.nextInt(), b = in.nextInt();
if (find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
} else{
int a = in.nextInt();
System.out.println(size[find(a)]);
}
}
}
}
食物链
合并集合
package 数据结构;
import java.io.BufferedInputStream;
import java.util.Scanner;
public class FoodChain {
private static final int N = 50010;
//l表示到根节点父节点的距离
private static int[] p = new int[N], l = new int[N];
private static int n, k;
public static int find(int x) {
if (p[x] != x) {
//先返回根节点
int t = find(p[x]);
//将父节点的距离加上后
l[x] += l[p[x]];
//最后压缩到根节点上
p[x] = t;
}
return p[x];
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
n = in.nextInt();
k = in.nextInt();
//并查集初始化
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int res = 0;
while (k-- != 0) {
int u = in.nextInt(), a = in.nextInt(), b = in.nextInt();
int pa = find(a), pb = find(b);
if (a > n || b > n) res++;
else if (u == 1) {
//跟前面的话导出的结果冲突
if (pa == pb && (l[b] - l[a]) % 3 != 0) {
res++;
}
//如果不冲突并且两棵树属于不同树，那么这句话就为弄假成真
else if (pa != pb) {
p[pa] = pb;
//pb需要赋成指定值
l[pa] = l[b] - l[a];
}
} else if (u == 2) {
//这里不能写成(l[a]-l[b]) % 3!=1,原因是包括了l[a]+1=l[b]的情形
if (pa == pb && (l[a] - l[b] - 1) % 3 != 0) {
res++;
} else if (pa != pb) {
p[pa] = pb;
l[pa] = l[b] - l[a] + 1;
}
}
}
System.out.println(res);
}
}
堆
手写一个堆
每棵子树的根节点是这棵子树的最小值
优先队列就是堆
down操作
向下调整一个堆，维持堆的性质
和子节点中较小的比较，看是否交换
//非递归写法
public static void down(int u){
int t = u;
while(true){
if(u*2<=size&&h[u*2]<h[t]) t = u*2;
if(u*2+1<=size&&h[u*2+1]<h[t]) t = u*2+1;
if(u!=t)
{
int temp = h[u];
h[u] = h[t];
h[t] = temp;
u=t;
}
else break;
}
}
//递归写法
public static void down(int u){
int t = u;
if(u*2<=size&&h[u*2]<h[t]) t = u*2;
if(u*2+1<=size&&h[u*2+1]<h[t]) t = u*2+1;
if(u!=t)
{
int temp = h[u];
h[u] = h[t];
h[t] = temp;
down(t);
}
}
up操作
向上调整一个堆 维持堆的性质
只和父节点比较是否，看是否交换
public static void up(int u){
while(u/2!=0&&h[u/2]>h[u]){
int temp = h[u];
h[u] = h[u/2];
h[u/2] = temp;
u = u/2;
}
}
核心操作
down建堆
for(int i = n/2;i>0;i--)down(i);
时间复杂度为O（n），直接插入为O（nlogn）
堆排序
package 数据结构;
import java.io.BufferedInputStream;
import java.util.Scanner;
public class HeapSort {
private static final int N = 100010;
private static int[] h = new int[N];
private static int size = 0;
public static void down(int u){
int t = u;
while(true){
if(u*2<=size&&h[u*2]<h[t]) t = u*2;
if(u*2+1<=size&&h[u*2+1]<h[t]) t = u*2+1;
if(u!=t)
{
int temp = h[u];
h[u] = h[t];
h[t] = temp;
u=t;
}
else break;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt(), m = in.nextInt();
for (int i = 1; i <= n; i++) {
h[i] = in.nextInt();
}
size = n;
for(int i = n/2;i>0;i--)down(i);
while(m--!=0){
int res = h[1];
h[1] = h[size];
size--;
down(1);
System.out.print(res+" ");
}
}
}
模拟堆
开辟第k个插入的点和下标的两个映射数组，这样两者求对应的值都是O（1）
迪克斯特拉算法用到这两个数组，其他情况不常用
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
private static final int N = 100010;
//ph得到下标,hp得到对应插入的目前个数
private static int[] h = new int[N], hp = new int[N], ph = new int[N];
private static int size = 0;
//传入数组的下标，用下标交换全局数组里对应下标的值
public static void heap_swap(int a, int b) {
int temp = h[a];
h[a] = h[b];
h[b] = temp;
temp = ph[hp[a]];
ph[hp[a]] = ph[hp[b]];
ph[hp[b]] = temp;
temp = hp[a];
hp[a] = hp[b];
hp[b] =temp;
}
public static void down(int u) {
int t = u;
while (true) {
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) {
heap_swap(u, t);
u = t;
} else break;
}
}
public static void up(int u) {
while (u / 2 != 0 && h[u / 2] > h[u]) {
heap_swap(u, u / 2);
u /= 2;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
//m表示目前插了几个节点
int n = in.nextInt(),m=0;
while (n-- != 0) {
String s = in.next();
if (s.equals("I")) {
int a = in.nextInt();
h[++size] = a;
m++;
//更新两个映射数组
ph[m]=size;hp[size]=m;
up(size);
}
else if(s.equals("PM")){
System.out.println(h[1]);
}
else if(s.equals("DM")){
heap_swap(1,size);
size--;
down(1);
}
else if(s.equals("D")){
int k = in.nextInt();
k = ph[k];
heap_swap(size,k);
size--;
//这里是down和up，如果删除最后一层元素，那么可能下移或者上移，否则下移
down(k);up(k);
}
else {
int k = in.nextInt(),x = in.nextInt();
k = ph[k];
h[k] = x;
//修改，可能改大或者改小
down(k);up(k);
}
}
}
}
Hash表
把一个大范围的数映射到小的数，按照冲突的解决方式分为开放寻址法和拉链法
mod的数一般取质数，且离2的整数幂尽可能远，这样冲突较小
离散化是一种特殊的哈希函数
虽然有链，但是每条链都不是很长，时间复杂度依然是O（1）
一般只有添加和查找操作，没有删除操作
如果要实现删除也不是真的实现删除，而是做标记
开放寻址法模板
一般开数组空间为映射范围的2~3倍
删除可以看做是查找的特殊一种
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int N = 200003, index = Integer.MAX_VALUE;
private static int[] h = new int[N];
public static void insert(int a) {
int k = find(a);
//一直找到可以插入的位置为止
while (h[k] == index) {
h[k] = a;
//找到后退出循环
break;
}
}
/**
* 查找一个数是否存在，如果不存在就返回它应该插入的位置
*
* @param a
* @return
*/
public static int find(int a) {
int idx = 0;
//先mod再加再mod
int k = (a % N + N) % N;
while (h[k] != index && h[k] != a) {
k++;
//写成N也行，循环查找
if (k == N + 1) k = 0;
}
//这里返回坐标比直接返回值要好，因为插入要用到下标
return k;
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
Arrays.fill(h, Integer.MAX_VALUE);
while (n-- != 0) {
String s = in.next();
if (s.equals("I")) {
int a = in.nextInt();
insert(a);
} else {
int a = in.nextInt();
if (h[find(a)] == a) System.out.println("Yes");
else System.out.println("No");
}
}
}
}
拉链法模板
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int N = 100003;
private static int[] h = new int[N], e = new int[N], ne = new int[N];
private static int idx = 0;
public static void insert(int a) {
int k = (a % N + N) % N;
e[idx] = a;
ne[idx] = h[k];
h[k] = idx++;
}
public static boolean query(int a) {
boolean flag = false;
int k = (a % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) {
if(e[i] == a) flag = true;
}
return flag;
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
Arrays.fill(h, -1);
while (n-- != 0) {
String s = in.next();
if (s.equals("I")) {
int a = in.nextInt();
insert(a);
} else {
int a = in.nextInt();
if (query(a)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}
字符串hash方式
字符串前缀hash法
P=131或13331，Q = 264是经验值，假设取这些值几乎没有冲突
应用
通过这种方式求得任一一个子串的hash值
不需要取膜，用unsigned longlong来存所有的h，溢出就自动去mod了
预处理字符串hash值
import java.io.*;
public class Main {
//P是数的进制，经验值取131或者13331
private static final int N = 100010, P = 131;
private static int m, n;
private static long[] h = new long[N], p = new long[N];
public static long getNum(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = in.readLine().split(" ");
//m为询问次数
int n = Integer.valueOf(s1[0]), m = Integer.valueOf(s1[1]);
String[] s2 = in.readLine().split(" ");
char[] str = s2[0].toCharArray();
p[0] = 1;
for (int i = 1; i <= n; i++) {
//预处理指数
p[i] = p[i - 1] * P;
//算hash值
h[i] = h[i - 1] * P + str[i - 1];
}
while (m-- != 0) {
String[] s3 = in.readLine().split(" ");
int l1 = Integer.parseInt(s3[0]), r1 = Integer.parseInt(s3[1]),
l2 = Integer.parseInt(s3[2]), r2 = Integer.parseInt(s3[3]);
if(getNum(l1,r1)==getNum(l2,r2)) System.out.println("Yes");
else System.out.println("No");
}
}
}
其他
AcWing查询hash，做相关题目
KMP可以用来做循环节，这个算法不能做循环节，除此之外基本都用这个算法