你也喜欢幸运字符串吗？、小蓝的01串

问题描述小蓝非常喜欢幸运字符串幸运字符串指的是字符串的一个前缀现在给定你一个长度为 nn 的字符串 SS要求你数出这个字符串中对于每个幸运字符串总共出现了多少次输入格式第一行给定一个正整数 nn 。第二行输入一个由小写字母组成的字符串表示字符串 SS 。输出格式每次输出一个正整数表示答案。输入案例6 abcabc样例输出9说明对于前缀 a,ab,abcabca,abca,abcabca,ab,abcabca,abca,abcabc 字符串中分别出现 2,2,2,1,1,12,2,2,1,1,1 所以答案为 22211192221119。评测数据规模对于 100100% 的评测数据1≤n≤2×1051≤n≤2×105。代码1OutOfMemoryErrorimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Main { static int N 2*100010; //static long a[]new long[N]; static int next[]new int[N];//该值是最长前缀后缀的长度 static int p[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); // String g[] br.readLine().split( ); // int nInteger.parseInt(g[0]),qInteger.parseInt(g[1]); String stringbr.readLine(); int mstring.length(); MapString, Integer mapnew HashMapString, Integer(); for (int i 0; i m; i) { for (int j i1; j m; j) { String tstring.substring(i,j); map.put(t,map.getOrDefault(t, 0)1); } } // for(String key:map.keySet()){ // System.out.println(key map.get(key)); // } long res0; for (int i 1; i m; i) { String tStringstring.substring(0,i); resmap.get(tString); } System.out.println(res); } }KMP优化import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N 2*100010; //static long a[]new long[N]; static int next[]new int[N];//该值是最长前缀后缀的长度 static int cnt[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); // String g[] br.readLine().split( ); // int nInteger.parseInt(g[0]),qInteger.parseInt(g[1]); String stringbr.readLine(); char c[]string.toCharArray(); getNext(c,n); //一个前缀s[0..i−1] 的出现次数等于 以它为最长前后缀的后缀缀个数 1自身 //cnt[i]表示s[0..i]的出现次数 cnt[next[i]-1]cnt[i] //比如 ab 出现在 abcab 的结尾是因为 abcab 这个前缀的后缀恰好是 ab。 // 也就是说 // ab 是 abcab 的 border即相等的真前缀和真后缀。 // // 所以如果一个前缀 A 是另一个前缀 B 的 border那么 B 出现的地方A 也会在 B 的末尾出现一次。 // 因此 //前缀 A 的总出现次数 A 自己作为前缀出现的那一次 所有以 A 为 border 的更长的前缀的出现次数。 for (int i 0; i n; i) { cnt[i]1;//每个前缀至少出现了一次 } for (int i n-1; i 0 ; i--) { if(next[i]0)cnt[next[i]-1]cnt[i]; } long res0; for (int i 0; i n; i) { rescnt[i]; } System.out.println(res); } static void getNext(char c[],int n){//求next数组 for (int i 1,j0; i n; i) { while(c[i]!c[j] j0){ jnext[j-1]; } if(c[i]c[j]){ j; } next[i]j; } } }小蓝的01串题目描述小蓝有一个只包含 00 和 11 字符串请你帮他算算这个字符串有多少个子串将 00 和 11 取反后再将整个子串反过来和原子串一样。输入描述输入第一行包含一个整数 nn(n≤5×105n≤5×105)表示字符串长度。第二行包含一个长度为 nn 的字符串 SSSS 只拥有 00、11 两种字符。输出描述输出仅一行包含一个整数表示答案。输入输出样例示例输入6 100100输出3代码1理论上超时import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N 2*100010; //static long a[]new long[N]; static int next[]new int[N];//该值是最长前缀后缀的长度 static int cnt[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); // String g[] br.readLine().split( ); // int nInteger.parseInt(g[0]),qInteger.parseInt(g[1]); String stringbr.readLine(); char c[]string.toCharArray(); //getNext(c,n); long res0; for (int i 0; i n; i) { for (int j i1; j n; j) { String tstring.substring(i,j); String revreverseXor(t); if(t.equals(rev))res; } } System.out.println(res); } static String reverseXor(String t){ char c[]t.toCharArray(); int mc.length; for (int i 0; i m; i) { if(c[i]1)c[i]0; else c[i]1; } // System.out.print(t:new String(c)\n); return new StringBuilder(new String(c)).reverse().toString(); } static void getNext(char c[],int n){//求next数组 for (int i 1,j0; i n; i) { while(c[i]!c[j] j0){ jnext[j-1]; } if(c[i]c[j]){ j; } next[i]j; } } }manachar优化import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N 1000010; //static long a[]new long[N]; static int next[]new int[N];//该值是最长前缀后缀的长度 static int mana[]new int[N]; static int p[]new int[N];//manachar的回文半径 public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); // String g[] br.readLine().split( ); // int nInteger.parseInt(g[0]),qInteger.parseInt(g[1]); String stringbr.readLine(); char c[]string.toCharArray(); //想要满足题意子串长度必须为偶数且对称位置互补 //如果把0变成-1 在每个字符前后都插入0 //我们可以套用manacher算法 将对应位置相等转变为对应位置加起来等于0 //100100: 0 1 0 -1 0 -1 0 1 0 -1 0 -1 0 //而且我们只需要关注0的位置就可以 找到的一定是偶数 int m0; mana[m]0; for (int i 0; i n; i) { if(c[i]0)mana[m]-1; else{ mana[m]1; } mana[m]0; } manacher(m,mana); long res0; for (int i 0; i m; i) { if(mana[i]0){ resp[i]/2; } } System.out.println(res); } static void manacher(int m,int mana[]){ int c0,r0;//表示当前的回文中心和回文右半径对应的边界 也就是子串对因的索引 p[0]1; for (int i 1; i m; i) { if(ic){ ci; } // c i p[i]Math.min(p[2*c-i],i-c);//在管辖的范围内和只截取在管辖的内的部分 //超出的部分 要向外枚举 while(i-p[i]-10 ip[i]1m mana[ip[i]1] mana[i-p[i]-1]0){ p[i]; } if(ip[i]r){ ci; rip[i]; } } } }