郑州网站建设廴汉狮网络,商城网站如何搭建,网站备案 新增,品牌关键词优化哪家便宜Manacher#xff08;马拉车#xff09;算法
作用#xff1a;在On的时间复杂度下#xff0c;求出字符串每个回文中心的最长回文半径 回文半径#xff1a;以回文中心为起点#xff0c;到回文串两端的距离 如#xff1a;# a # b # a # 以b为回文中心#xff0c;最长回文半…Manacher马拉车算法
作用在On的时间复杂度下求出字符串每个回文中心的最长回文半径 回文半径以回文中心为起点到回文串两端的距离 如# a # b # a # 以b为回文中心最长回文半径就是 4可以根据个人习惯选择是否将回文中心包括 如果回文字符串长度为偶数那么回文中心就无法正好落在某个字符上所以可以在每个字符之间添加一个“#”做前置处理包括字符串首尾 对于求一个字符串中每个字符的最长回文半径暴力做法是使用两层循环遍历字符串的每个字符以遍历到的字符为中心向两边扩散
public class Main {public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));String s br.readLine();s getNew(s);//每个位置的最长回文半径int[]r new int[s.length()];for (int i 0;i s.length();i) {while (i-r[i] 0 ir[i] s.length() s.charAt(i - r[i]) s.charAt(i r[i])) r[i];}for (int i 0; i s.length(); i) {System.out.print(s.charAt(i) );}System.out.println();for (int i 0; i s.length(); i) {System.out.print(r[i] );}}public static String getNew(String str) {String s #;for (int i 0;i str.length();i) {s str.charAt(i) #;}return s;}
}思路
利用回文串的对称性和之前遍历过的已知的回文串减少中心扩散的次数这里我们要维护一个使区间右端最靠右的区间
设有字符串SS的l到r区间是回文串mid为回文中心现要求以i为回文中心的最长回文半径
i在区间 [ l , r ] 内
j为i关于mid的对称点那么 以 j 为中心的回文串在 [ l , r] 内 易知r [ i ] r [ j ] 以 j 为中心的回文串有部分在[ l , r ] 外 r [ j ] 中超出 l 的那部分肯定和 r 右边不同所以r [ i ] j - l 1 r - i 1 以 j 为中心的回文串左边界与 l 重合 这时r [ i ] 是可以大于 r [ j ] 的就要用中心扩散来接着求 r [ i ]
i在区间 [ l , r ] 外
这时只能用中心扩散来求 r [ i ]
示例洛谷P3805 【模板】manacher
求最大回文子串长度
import java.io.*;public class Main{static final int N 22000005;public static void main(String[]args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));String s br.readLine();char[]c s.toCharArray();char[]sc new char[N];int[]d new int[N];sc[0] #;int cnt 0;for(int i 0;i c.length;i) {sc[cnt] c[i];sc[cnt] #;}int r 0,len 0,mid 0;for(int i 1;i cnt;i) {if(i r) d[i] Math.min(d[(mid 1) - i],r - i 1);else d[i] 1;while(i - d[i] 0 sc[id[i]] sc[i - d[i]]) d[i];//维护最靠右区间if(i d[i] - 1 r) {mid i;r i d[i] - 1;}//这里d[i] - 1是将子串中的‘#’去掉的长度len Math.max(len,d[i] - 1);}System.out.println(len);}
}
