• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      Manacher算法在計算最長回文子串長度中的應用

      2017-11-16 23:47:32唐高陽
      科技視界 2017年18期

      唐高陽

      【摘 要】本文首介紹了如何運用Manacher算法在線性時間內(nèi)找到一個字符串的最長回文子串。

      【關(guān)鍵詞】Manacher算法;回文串;回文子串

      The Manacher algorithm is used to calculate the length of the longest return string

      TANG Gao-yang

      (Shenyang institute of science and technology, Shenyang, Liaoning 110168)

      【Abstract】This paper first introduces a method for finding the longest palindrome subsrting in linear time by the Manacher Algorithm.

      【Key words】Manacher algorithm;Palindrome srting;Palindrome subsrting

      1 遍歷

      因為奇回文和偶回文在判斷時比較麻煩,所以對str進行處理,把每個字符開頭、結(jié)尾和中間插入一個特殊字符′#′來得到一個新的字符串數(shù)組。比如str=″bcbaa″,處理后為″#b#c#b#a#a#″,然后從每個字符左右擴出去的方式找最大回文子串就方便多了。對奇回文來說,不這么處理也能通過擴的方式找到,比如″bcb″,從′c′開始向左右兩側(cè)擴出去能找到最大回文。處理后為″#b#c#b#″,從′c′開始向左右兩側(cè)擴出去依然能找到最大回文。對偶回文來說,不處理而直接通過擴的方式是找不到的,比如″aa″,因為沒有確定的軸,但是處理后為″#a#a#″,就可以通過從中間的′#′擴出去的方式找到最大回文。所以通過這樣的處理方式,最大回文子串無論是偶回文還是奇回文,都可以通過統(tǒng)一的“擴”過程找到,解決了差異性的問題。同時要說的是,這個特殊字符是什么無所謂,甚至可以是字符串中出現(xiàn)的字符,也不會影響最終的結(jié)果,就是一個純輔助的作用。

      具體的處理過程請參看如下代碼中的manacherString方法。

      public char[] manacherString(String str) {

      char[] charArr=str.toCharArray();

      char[] res=new char[str.length()*2+1];

      int index=0;

      for (i=0;I !=res.length;i++){

      res[i]=(i&1)==0?#:charArr[index++];

      }

      Return res;

      }

      2 優(yōu)化

      假設str處理之后的字符串記為charArr。對每個字符(包括特殊字符)都進行“優(yōu)化后”的擴過程。

      3 擴過程

      只要能夠從左到右依次算出數(shù)組pArr每個位置的值,最大的那個值實際上就是處理后的charArr中最大的回文半徑,根據(jù)最大的回文半徑,再對應回原字符串的話,整個問題就解決了。步驟3就是從左到右依次計算出pArr數(shù)組每個位置的值的過程。

      (1)假設現(xiàn)在計算到位置i的字符charArr[i],在i之前位置的計算過程中,都會不斷地更新pR和index的值,即位置i之前的index這個回文中心擴出了一個目前最右的回文邊界pR。

      (2)如果pR-1位置沒有包住當前的i位置。比如“#c#a#b#a#c#”,計算到charArr[1]==c時,pR為1。也就是說,右邊界在1位置,1位置為最右回文半徑即將到達但還沒有達到的位置,所以當前的pR-1位置沒有包住當前的i位置。此時和普通做法一樣,從i位置字符開始,向左右兩側(cè)擴出去檢查,此時的“擴”過程沒有獲得加速。

      (3)如果pR-1位置包住當前的i位置。比如“#c#a#b#a#c#”,計算到charArr[6…10]時,pR都為11,此時pR-1包住了位置6-10。這種情況下,檢查過程是可以獲得優(yōu)化的,這也是manacher算法的核心內(nèi)容。

      4 進階問題

      按照步驟3的邏輯從左到右計算出pArr數(shù)組,計算完成后再遍歷一遍pArr數(shù)組,找出最大的回文半徑,假設位置i的回文半徑最大,即pArr[i]==max。但max只是charArr的最大回文半徑,還得對應回原來的字符串,求出最大回文半徑的長度(其實就是max-1)。在charArr中位置3的回文半徑最大,最大值為4(即pArr[3]==4),對應原字符串的最大回文子串長度為4-1=3。

      Manacher算法時間復雜度是O(N)的證明。雖然我們可以很明顯地看到Manacher算法與普通方法相比,在擴出去檢查這一行為上有明顯的優(yōu)化,但如何證明該算法的時間復雜度就是O(N)呢?關(guān)鍵之處在于估算擴出去檢查這一行為發(fā)生的數(shù)量。原字符串在處理后的長度由N變?yōu)?N,從步驟3的主要邏輯來看,要么在計算一個位置的回文半徑時完全不需要擴出去檢查,比如,步驟3的中3)介紹的情況一和情況二,都可以直接獲得位置i的回文半徑長度;要么每一次擴出去檢查都會讓回文半徑到達更右的位置,當然會使pR更新。然而pR最多是從-1增加到2N(右邊界),并且從來不減小,所以擴出去檢查的次數(shù)就是O(N)的級別。所以Manacher算法時間復雜度是O(N)。具體請參看如下代碼中的maxLcpsLength方法。

      public static int maxLcpsLength(String str) {

      if (str == null || str.length() == 0) {endprint

      return 0;

      }

      char[] charArr = manacherString(str);

      int[] pArr = new int[charArr.length];

      int index = -1;

      int pR = -1;

      int max = Integer.MIN_VALUE;

      for (int i = 0; i != charArr.length; i++) {

      pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;

      while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {

      if (charArr[i + pArr[i]] == charArr[i - pArr[i]])

      pArr[i]++;

      else {

      break;

      }

      }

      if (i + pArr[i] > pR) {

      pR = i + pArr[i];

      index = i;

      }

      max = Math.max(max, pArr[i]);

      }

      return max - 1;

      }

      在字符串的最后添加最少字符,使整個字符串都成為回文串,其實就是查找在必須包含最后一個字符的情況下,最長的回文串是什么。那么之前不是最長回文子串的部分逆序過來,就是應該添加的部分。比如“abcd123321”,在必須包含最后一個字符的情況下,最長的回文子串是 “123321”,之前不是最長回文子串的部分是“abcd”,所以末尾應該添加的部分就是“dcba”。那么只要把manacher算法稍作修改就可以。具體改為:從左到右計算回文半徑時,關(guān)注回文半徑最右即將到達的位置(pR),一旦發(fā)現(xiàn)已經(jīng)到達最后(pR == charArr.length),說明必須包含最后一個字符的最長回文半徑已經(jīng)找到,直接退出檢查過程,返回該添加的字符串即可。具體過程參看如下代碼中的shortestEnd方法。

      public static String shortestEnd(String str) {

      if (str == null || str.length() == 0) {

      return null;

      }

      char[] charArr = manacherString(str);

      int[] pArr = new int[charArr.length];

      int index=-1;

      int pR=-1;

      int maxContainsEnd = -1;

      for (int i = 0; i != charArr.length; i++) {

      pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;

      while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {

      if (charArr[i + pArr[i]] == charArr[i - pArr[i]])

      pArr[i]++;

      else {

      break;

      }

      }

      if (i + pArr[i] > pR) {

      pR = i + pArr[i];

      index = i;

      }

      if (pR == charArr.length) {

      maxContainsEnd = pArr[i];

      break;

      }

      }

      char[] res = new char[str.length() - maxContainsEnd + 1];

      for (int i = 0; i < res.length; i++) {

      res[res.length - 1 - i] = charArr[i * 2 + 1];

      }

      return String.valueOf(res);

      }

      5 結(jié)果與分析

      Manacher算法是由Glenn Manacher于1975年首次發(fā)明的,比起能夠解決該問題的其他算法,Manacher算法算比較好理解和實現(xiàn)的。

      【參考文獻】

      [1]Bruce Eckel.《Java編程思想》.機械工業(yè)出版社.2007.6.1.

      [2]梁勇.《Java語言程序設計(基礎篇)》.機械工業(yè)出版社2015.7.1.

      [3]梁勇.《Java語言程序設計(進階篇)》.機械工業(yè)出版社.2016.10.1.

      [4]Thomas H.Cormen;Charles E.Leiserson;Ronald L.Rivest;Clifford Stein 《算法導論》機械工業(yè)出版社.2013.7.1.

      [5]Mark Allen Weiss.《數(shù)據(jù)結(jié)構(gòu)與算法分析 Java語言描述》.機械工業(yè)出版社.2009.1.1.

      [6]Robert Sedgewick. Kevin Wayne.《算法(第4版)》人民郵電出版社.2012.10.1.endprint

      巴楚县| 丰顺县| 南通市| 赫章县| 安远县| 盐山县| 石家庄市| 寻乌县| 泰安市| 宁乡县| 桃园县| 扎兰屯市| 德阳市| 宜川县| 汉阴县| 高邑县| 定襄县| 民县| 永川市| 张家界市| 罗山县| 濮阳县| 南平市| 遂昌县| 石柱| 榆林市| 枣阳市| 辽宁省| 平安县| 昭觉县| 青神县| 扎兰屯市| 若尔盖县| 临汾市| 富源县| 万源市| 土默特左旗| 香格里拉县| 泰州市| 民和| 辉县市|