Manacher算法---解决回文串相关问题（Java实现）

本文主要是介绍Manacher算法---解决回文串相关问题（Java实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、Manacher算法介绍

二、代码实现

---

一、Manacher算法介绍

Manacher算法是用来解决一些关于回文串的问题。

计算字符串中每个位置作为回文中心的回文半径的算法，位置i的回文半径用p[i]表示，意思是在转换后的字符串中[i-p[i]+1,i+p[i]-1]是回文的

一般来说偶数长度是不会有回文中心的，因为没有意义。所以Mancher算法就是将原来的字符串变成有回文半径的字符串。可以通过添加字符，注意开头和结尾字符不一样！如ABBA->!#A#B#B#A#+

二、代码实现

 例题：最长回文子串

import java.math.BigInteger;
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);String s=scanner.next();System.out.println(mancher(s));}public static int mancher(String s){StringBuilder str=new StringBuilder();str.append('!');for(int i=0;i<s.length();i++){str.append('#');str.append(s.charAt(i));}str.append("#+");int[] p=new int[str.length()];//r：所有的回文子串中最大的右边界//c：对应的中心点int c=0,r=0,max=-1;for(int i=1;i<str.length()-1;i++){p[i]=i<r?Math.min(r-i,p[2*c-i]):1;while(str.charAt(p[i]+i)==str.charAt(i-p[i])){p[i]++;}if(p[i]+i>r){r=p[i]+i;c=i;}//真是的长度是p[i]-1，因为我们添加了字符，不是原来的字符串max=Math.max(p[i]-1,max);}return max;}
}

这篇关于Manacher算法---解决回文串相关问题（Java实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---