字符串哈希给定一个长度为 n 的字符串再给定 m 个询问每个询问包含四个整数 l1,r1,l2,r2请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式第一行包含整数 n 和 m表示字符串长度和询问次数。第二行包含一个长度为 n 的字符串字符串中只包含大小写英文字母和数字。接下来 m 行每行包含四个整数 l1,r1,l2,r2表示一次询问所涉及的两个区间。注意字符串的位置从 1 开始编号。输出格式对于每个询问输出一个结果如果两个字符串子串完全相同则输出Yes否则输出No。每个结果占一行。数据范围1≤n,m≤105输入样例8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2输出样例Yes No Yes如果我们在这个q字查询中采用暴力做法那时间复杂度会达到Oq*n必然会超时。我们可以把字符串中的每一个字符都转换成一个p进制的数字 让计算机比较数字比比较字符串好太多了 数字可以整体比较但是字符串必须一个一个来进行比较我们可以将字符串中的每个字符转化为一个p进制的数字假设一个字符串已经转化成了数字字符串下图中。如果我们想计算一个子串的值可以根据res的值以及p次方来进行计算。我们可以先预处理出一个b数组存放p的幂次P一般取131或13331。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N100010,p131; static int res[]new int[N]; static int b[]new int[N]; //static boolean f[]new boolean[5050]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()); int mInteger.parseInt(st.nextToken()); char c[]( br.readLine()).toCharArray(); //同时计算res和b数组 b[0]1;//p的零次为1 res[0]c[0]; for (int i 1; i n; i) { b[i]b[i-1]*p; res[i]res[i-1]*pc[i]; } for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int l1Integer.parseInt(st.nextToken()),r1Integer.parseInt(st.nextToken()); int l2Integer.parseInt(st.nextToken()),r2Integer.parseInt(st.nextToken()); int z1getHash(l1,r1),z2getHash(l2,r2); if(z1z2){ bw.write(Yes\n); }else{ bw.write(No\n); } } br.close(); bw.flush(); bw.close(); } static int getHash(int l,int r){ return res[r]-res[l-1]*b[r-l1]; } }最长回文子串题目描述给定一个字符串 SS请你求出 SS 的最长回文子串。输入描述输入仅一行包含一个字符串 SS。1≤∣S∣≤5×1051≤∣S∣≤5×105保证 SS 只包含小写字母、大写字母、数字。输出描述输出共 11 行包含一个整数表示答案。输入输出样例示例 1输入aa1ABA1b输出5运行限制最大运行时间2s最大运行内存: 256M首先我们要明确回问中心和回问半径的概念比如abcba 它的回文中心是c回文半径是2。如果是abba那他的回文中心就是bb回文半径就是1我们以每以字符串的每个字符为中心不断的向外扩展回纹半径也就是使得回纹半径越来越大看是否是回文串。具体思路就是先是最外面一层遍历每个字符然后第二层循环。枚举回文半径的长度那么在两层循环中就可以确定一个子串 我们只需要判断这个子串的前半部分和反转后的后半部分是否相等就可以是否相等可以借助哈希函数的值这样的时间复杂度为On^2但是我们知道当一个字符串的回文半径是五的时候那么比它小的回文半径一定也是回文串所以回文半径满足二分的性质所以在上面第二层没去。回文半径的长度的时候就可以采用二分这样时间复杂度就降为了On log n。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int N5*100010,p131,mod(int)(1e9)7; static int pre[]new int[N];//pre[1]1 pre[2]16 pre[3]162 static int b[]new int[N]; static int suffi[]new int[N];//suffi[1]261 suffi[2]26 suffi[3]2 public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); char c[]( br.readLine()).toCharArray(); int nc.length-1; b[0]1; for (int i 1; i n; i) { b[i](int)(((long)b[i-1]*p)%mod); pre[i](int)(((long)pre[i-1]*pc[i])%mod); } for (int i n; i 0; i--) { suffi[i](int)(((long)suffi[i1]*pc[i])%mod); } int res1; //单字符中心的回文串 for (int i 1; i n; i) { int left0; int rightMath.min(i-1, n-i); while(leftright){ int mid(leftright1)1; int li-mid; int rimid; if(getHash(l,i-1)getRevHash(i1,r))leftmid; else rightmid-1; } resMath.max(res, 2*left1); } //双字符的回文串 for (int i 1; i 1 n; i) { if(c[i]!c[i1])continue; int left0; int rightMath.min(i-1, n-(i1)); while(leftright){ int mid(leftright1)1; int li-mid; int ri1mid; if(getHash(l,i-1)getRevHash(i2,r))leftmid; else rightmid-1; } resMath.max(res,2*left2); } bw.write(res); br.close(); bw.flush(); bw.close(); } static int getHash(int l,int r){ return (int)(((pre[r]-(long)pre[l-1]*b[r-l1])%modmod)%mod); } static int getRevHash(int l,int r){ return (int)(((suffi[l]-(long)suffi[r1]*b[r-l1])%modmod)%mod); } }Manacher题目描述给出一个只由小写英文字符 a,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度 。字符串长度为 n。输入格式一行小写英文字符 a,b,c,⋯,y,z 组成的字符串 S。输出格式一个整数表示答案。输入输出样例输入 #1复制aaa输出 #1复制3说明/提示1≤n≤1.1×107。两端以及间隔加上#可以证明Manacher算法的时间复杂度为O(2n)也就是O(n)。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int N11*1000010; static int p[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); // StringTokenizer stnew StringTokenizer(br.readLine()); // // int nInteger.parseInt(st.nextToken()); // int mInteger.parseInt(st.nextToken()); char c[]( br.readLine()).toCharArray(); char cc[]new char[2*c.length]; int ind1; cc[ind]#; for (int i 1; i c.length; i) { cc[ind]c[i]; cc[ind]#; } //将原字符串添加相应的符号之后我们不需要再区分单字符的回文中心还是双字符的回文中心 //如果我们想找单字符的回文中心 可以字符为中心就可以找到所有的回文串 //如果我们想找双字符的回文中心 可以#为中心就可以找到所有的回文串 int C1,R0;//C表示回文中心 R表示最有价值的有边界 for (int i 1; i ind; i) { if(iR){ p[i]Math.min(p[2*C-i], R-i); //为什么要取min呢是因为 //C-r C Cr // 2*C-i i //当我们计算i点的时候我们会利用其对称点2c-i的值 //但是其对称点可能会超出其左边界c-r 如果超了的话那取值就是r减i。 //如果没有超出那答案就是p[2*C-i] } //如果说p[i]和p[2*C-i]的值是一样的 则此循环一定不会执行 //否则就会执行循环 也就是暴力的向两端枚举 while(i-p[i]-10 ip[i]1 ind cc[i-p[i]-1]cc[ip[i]1]){ p[i]; } if(ip[i]R){ Rip[i]; Ci; } } int res1; for (int i 1; i ind; i) { resMath.max(res, p[i]); } bw.write(res); br.close(); bw.flush(); bw.close(); } }