java---哈希表---字符串哈希每日一道算法2022.8.19
题目
给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同
字符串中只包含大小写英文字母和数字
输入
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出
Yes
No
Yes
public class 哈希表_字符串哈希 {
//初始化,P代表的是进制数,str储存的是a=1,b=2,c=3这样的,h存储的是字符串的前缀哈希值,p存储的是P进制值换算为十进制的值
public static int N = 100010, P = 131;
public static long[] h = new long[N], p = new long[N];
public static void main(String[] args) throws IOException {
//初始化,n是字符串长度,m是操作次数,s是字符串
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
String s = in.next();
p[0] = 1;
//切记切记,这里看好p的大小写
//str[i] - 'a' 1相当于拿到a-a=0,0 1=1,相当于a=1,b=2,c=3
for (int i = 1; i<=n; i ) {
p[i] = p[i-1] * P;
h[i] = h[i-1] * P (s.charAt(i-1)-'a' 1);
}
//操作部分
while (m-- > 0) {
int l1 = in.nextInt(), r1 = in.nextInt();
int l2 = in.nextInt(), r2 = in.nextInt();
//判断字串和字串的前缀哈希值是否相同
if (get(l1, r1) == get(l2, r2)) {System.out.println("Yes");}
else {System.out.println("No");}
}
}
//利用前缀和找到区间和,再进行右移操作,就能得到字串的前缀哈希值了
public static long get(int l, int r){
return h[r] - h[l-1]*p[r-l 1];
}
}
抱歉今天更新这么晚,花了太多不该花的时间,经历了没理解题->没理解核心公式->思路全理解了但是代码一直出bug,从晚上8点弄到现在终于AC,等我什么时候复习到这里的时候我再把讲解补上吧,太累了,睡了
声明:算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfijfg
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01