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

问题描述

小蓝非常喜欢幸运字符串，幸运字符串指的是字符串的一个前缀，现在给定你一个长度为 nn 的字符串 SS，要求你数出这个字符串中对于每个幸运字符串总共出现了多少次？

输入格式

第一行给定一个正整数 nn 。

第二行输入一个由小写字母组成的字符串表示字符串 SS 。

输出格式

每次输出一个正整数，表示答案。

输入案例

6 abcabc

样例输出

9

说明

对于前缀 a,ab,abc，abca,abca,abcabca,ab,abc，abca,abca,abcabc 字符串中分别出现 2,2,2,1,1,12,2,2,1,1,1 所以答案为 2+2+2+1+1+1=92+2+2+1+1+1=9。

评测数据规模

对于 100100% 的评测数据：

1≤n≤2×1051≤n≤2×105。

代码1（OutOfMemoryError）

import 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 n=Integer.parseInt(br.readLine()); // String g[] = br.readLine().split(" "); // int n=Integer.parseInt(g[0]),q=Integer.parseInt(g[1]); String string=br.readLine(); int m=string.length(); Map<String, Integer> map=new HashMap<String, Integer>(); for (int i = 0; i < m; i++) { for (int j = i+1; j <= m; j++) { String t=string.substring(i,j); map.put(t,map.getOrDefault(t, 0)+1); } } // for(String key:map.keySet()){ // System.out.println(key+" "+map.get(key)); // } long res=0; for (int i = 1; i <= m; i++) { String tString=string.substring(0,i); res+=map.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 n=Integer.parseInt(br.readLine()); // String g[] = br.readLine().split(" "); // int n=Integer.parseInt(g[0]),q=Integer.parseInt(g[1]); String string=br.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 res=0; for (int i = 0; i < n; i++) { res+=cnt[i]; } System.out.println(res); } static void getNext(char c[],int n){//求next数组 for (int i = 1,j=0; i < n; i++) { while(c[i]!=c[j] && j>0){ j=next[j-1]; } if(c[i]==c[j]){ j++; } next[i]=j; } } }

小蓝的01串

题目描述

小蓝有一个只包含 00 和 11 字符串，请你帮他算算这个字符串有多少个子串将 00 和 11 取反后，再将整个子串反过来和原子串一样。

输入描述

输入第一行包含一个整数 nn(n≤5×105n≤5×105)，表示字符串长度。

第二行包含一个长度为 nn 的字符串 SS，SS 只拥有 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 n=Integer.parseInt(br.readLine()); // String g[] = br.readLine().split(" "); // int n=Integer.parseInt(g[0]),q=Integer.parseInt(g[1]); String string=br.readLine(); char c[]=string.toCharArray(); //getNext(c,n); long res=0; for (int i = 0; i < n; i++) { for (int j = i+1; j <= n; j++) { String t=string.substring(i,j); String rev=reverseXor(t); if(t.equals(rev))res++; } } System.out.println(res); } static String reverseXor(String t){ char c[]=t.toCharArray(); int m=c.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,j=0; i < n; i++) { while(c[i]!=c[j] && j>0){ j=next[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 n=Integer.parseInt(br.readLine()); // String g[] = br.readLine().split(" "); // int n=Integer.parseInt(g[0]),q=Integer.parseInt(g[1]); String string=br.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 m=0; 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 res=0; for (int i = 0; i < m; i++) { if(mana[i]==0){ res+=p[i]/2; } } System.out.println(res); } static void manacher(int m,int mana[]){ int c=0,r=0;//表示当前的回文中心和回文右半径对应的边界 也就是子串对因的索引 p[0]=1; for (int i = 1; i < m; i++) { if(i>c){ c=i; } // c i p[i]=Math.min(p[2*c-i],i-c);//在管辖的范围内和只截取在管辖的内的部分 //超出的部分 要向外枚举 while(i-p[i]-1>=0 && i+p[i]+1<m && mana[i+p[i]+1] +mana[i-p[i]-1]==0){ p[i]++; } if(i+p[i]>r){ c=i; r=i+p[i]; } } } }