Manacher演算法及其擴展-有解無憂

文章目錄

- - - 回文字串：
    - 最長回文字串問題
    - - 有啥用？
    - 暴力解最長回文問題（ O ( N 2 ) O(N^2) O(N2)）
  - Manacher演算法O(N)
  - - 存盤的資訊
    - 幾種情況
    - 代碼

回文字串：

正著看反著看是一樣的
abccba abcba 存在一個軸對稱

最長回文字串問題

在一個字串中找到最長回文字串，而manacher演算法就是去找這個最長回文字串，

有啥用？

DNA序列回文基因序列有一些生理學意義

暴力解最長回文問題（ O ( N 2 ) O(N^2) O(N2)）

ab|ab 按照虛軸對稱

ababa 按照實軸中間的a對稱

遍歷每個實軸與虛軸，分別向兩邊擴展，存最長的

public static String getmaxstr(String s)
	
	{
		int maxlength=0;
		String  maxstr="";
		//從每一個軸擴展 包含實軸（是一個數，找奇數最長回文字串）  和虛軸（找偶數最長回文字串）
		for(int i=0;i<s.length();i++)
		{
			
			//以該字母為實軸
			int m=i;
			int n=i;
		
			while(m>=0&&n<s.length()&&s.charAt(m)==s.charAt(n))
			{
				if(n-m+1>maxlength)
				{
					maxlength=n-m+1;
					maxstr=s.substring(m, n+1);
				}
				m-=1;
				n+=1;
			}
			
			
			//以該字母后面為虛軸
			 m=i;
			 n=i+1;
			 
			 while(m>=0&&n<s.length()&&s.charAt(m)==s.charAt(n))
				{
					if(n-m+1>maxlength)
					{
#### #### 						maxlength=n-m+1;
						maxstr=s.substring(m, n+1);
					}
					m-=1;
					n+=1;
				}
		}
		return maxstr;
	}

Manacher演算法O(N)

其存盤一定資訊，加速上述思路的擴展程序，存取必要資訊，達到線性時間（與kmp類似哈）

加速tips的理解：

存盤的資訊

回文半徑陣列（以每一位為中心的回文字串長度）
r（最遠的右邊界）
c（最遠的右邊界的中心點）

幾種情況

i在r外的時候沒有任何優化
i在r內的時候若鏡面無法完全包含，我們直接跳到鏡面外的字母開始更新就行
i在r內的時候若鏡面完全包含，我們沒必要拓展這個字母

代碼

	//tested
	//abcd->#a#b#c#d#
	public static char[] tostrx(String str)
	{
		char[] strx=new char[2*str.length()+1];
		int l=0;
		for(int i=0;i<strx.length;i++)
		{
			if(i%2==0)
			{
				strx[i]='#';
			}
			else {
				strx[i]=str.charAt(l);
				l+=1;
			}
		}
		return strx;
	}
	
	
	//tested
	//檢測i是否在陣列x(長度為l)越界
	public static boolean isvalid(int i,int l)
	{
		if(i>=0&&i<l)
			return true;
		return false;
	}
	
	
	
	
	
	
	//tested
	//回傳該節點的最大回文字串長度
	public static int expand(char[] strx,int i,int j)//以i節點為中心，從j節點開始擴展
	{
		while(isvalid(j, strx.length)&&isvalid(2*i-j,strx.length)&&strx[j]==strx[2*i-j])
		{
			j+=1;
		}
		j-=1;
		return 2*(j-i)+1;
		
	}
	
	
	//tested
	//得到最大回文字串（去掉#）
	public static String str(char[] t,int[] parax)
	{
		int maxi=-1;
		int max=-1;
		for(int i=0;i<parax.length;i++)
		{
			if(parax[i]>max&&!(i%2==0&&parax[i]==1))
			{
				max=parax[i];
				maxi=i;
			}
		}
		String str=tostr(t, maxi-(max-1)/2, maxi+(max-1)/2);
		return str;
	}
	
	
	
	//manacher演算法
	public static String manacher(String str)
	{
		char[] strx=tostrx(str);
		int[] parax=new int[strx.length];//存取每一位的回文字串的最大長度
		int c=-1;
		int r=-1;//存取最遠右邊界
		
		for(int i=0;i<strx.length;i++)
		{
			if(i<r)
			{
				//parax[2*c-i]-1)/2+i  由鏡像節點得到當前節點的右邊界
				if((parax[2*c-i]-1)/2+i<r)//在鏡面內
				{
					parax[i]=parax[2*c-i];
				}
				else {
					parax[i]=expand(strx, i,r);
				}
				
			}
			else {
				parax[i]=expand(strx, i, i+1);
			}
		}
		
		String string=str(strx,parax);
		
		return string;
		
		
	}
	
	//tested
	//給定#a#b#c#d#  第幾位到第幾位  截取并洗掉#
	public static String tostr(char[] strx,int a,int b)
	{
		String str="";
		for(int i=a;i<=b;i++)
		{
			if(i%2!=0)
			{
				str=str+strx[i];
			
			}
		}
		return str;
	}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246925.html

標籤：其他

上一篇：FUSB302 PD物理層開發

下一篇：1467D. Sum of Paths(妙用dp的含義)