Circular Palindromes

作爲HackerRank challenge的一部分，我一直試圖解決圓形迴文的問題。Circular Palindromes

傳統的迴文問題基本上是在一個更大的字符串中找到最長對稱子字符串（迴文）的長度。在此hackerRank challenge中，較大的字符串的長度限制爲10 。它還通過要求我們找到每個旋轉字符串的長度來增加另一層複雜性。

類似的問題已經發布here，但我無法提取足夠的信息來讓我的代碼工作足夠快。

我寫了下面的Java代碼，這是Manacher's algorithm的修改在旋轉方面：

package cards.myb.algorithms; 

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.lang.management.ManagementFactory; 
import java.lang.management.ThreadMXBean; 
import java.math.*; 
import java.util.regex.*; 

public class CircularPalindrome { 

    public static void main(String[] args) { 

     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 

     boolean use_manacher = true; 
     int N = 0; 
     String S = ""; 
     String inputFile = "D:\\Home\\Java\\AlgorithmPractice\\input16.txt"; 
     String solutionFile = "D:\\Home\\Java\\AlgorithmPractice\\output16.txt"; 

     System.out.println("Reading file " + inputFile); 
     File file = new File(inputFile); 
     try { 
      FileInputStream fis = new FileInputStream(file); 
      BufferedReader in = new BufferedReader(new InputStreamReader(fis)); 
      N = Integer.valueOf(in.readLine()); 
      S = in.readLine(); 
      in.close(); 
     } catch(IOException e) { 
      e.printStackTrace(); 
      return; 
     } 

     // Convert string to char for efficiency 
     char[] sArr = S.toCharArray(); 

     // Start timer 
     ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean(); 
     long tStartNS = threadMXBean.getCurrentThreadCpuTime(); 
     System.out.println("Starting clock"); 

     // Allocate space for Sk, k=0...N-1 
     int[] lengths = new int[N]; 
     int[] plenEvenArr = new int[N]; 
     int[] plenOddArr = new int[N]; 

     // ******************************************** 
     // Part 1 : Even palindromes 
     // ******************************************** 
     int best_right = N-1, best_left = 0, best_plen = 0; 
     for(int i=0; i<N; i++) { 
      // i points to the position at the palindrome center (between two elements) 

      boolean do_loop = true; 
      int left, right, plen; 

      // Mirror image optimization 
      // Manacher's algorithm 
      if(!use_manacher || i > best_right) { 
       left = i; 
       right = (i-1+N)%N; 
       plen = 0; 
       //System.out.println("plen=" + plen + ", right=" + right + ", left=" + left); 
      } else { 
       int i2 = (best_left + best_right - i + 1 + N) % N; 

       //System.out.println("i=" + i + ", best_left = " + best_left + ", best_right=" + best_right + ", i2=" + i2); 

       if(i2 >= i) { 
        left = i; 
        right = (i-1+N)%N; 
        plen = 0; 
        //System.out.println("plen=" + plen + ", right=" + right + ", left=" + left); 
       } else if(plenEvenArr[i2] < ((best_right - i + 1 + N) % N) * 2) { 
        plen = plenEvenArr[i2]; 
        do_loop = false; 
        left = right = 0; // Avoid warnings 
        //System.out.println("use mirror image plenArr[i2]=" + plenArr[i2]); 
       } else { 
        plen = ((best_right - i + 1 + N) % N) * 2; 
        right = best_right; 
        left = (best_right - plen + 1 + N) % N; 
        //System.out.println("start from plen=" + plen + ", right=" + right + ", left=" + left); 
       } 
      } 

      // Find maximum even palindrome with center at i 
      for(; do_loop && plen < N-1; plen += 2) { 
       char expandleft = sArr[(left - 1 + N) % N]; 
       char expandright = sArr[(right + 1) % N]; 
       if(expandleft == expandright) { 
        left = (left - 1 + N) % N; 
        right = (right + 1) % N; 
       } else 
        break; 
      } 

      plenEvenArr[i] = plen; 

      // Keep track of best 
      if(plen > best_plen) { 
       best_right = right; 
       best_left = left; 
       best_plen = plen; 
      } 

     } 

     long tEvenNS = threadMXBean.getCurrentThreadCpuTime(); 

     // ******************************************** 
     // Part 2 : Odd palindromes 
     // ******************************************** 
     best_right = 0; best_left = 0; best_plen = 1; 
     for(int i=0; i<N; i++) { 
      // i points to the middle element of the palindrome 

      boolean do_loop = true; 
      int left, right, plen; 

      // Mirror image optimization 
      // Manacher's algorithm 
      if(!use_manacher || i > best_right) { 
       left = right = i; 
       plen = 1; 
        // System.out.println("plen=" + plen + ", right=" + right + ", left=" + left); 
      } else { 
       int dist_to_best_right = (best_right - i + N) % N; 
       int i2 = (best_left + dist_to_best_right) % N; 
       int plen_best = dist_to_best_right * 2 + 1; 

       // System.out.println("i=" + i + ", best_left = " + best_left + ", dist_to_best_right=" + dist_to_best_right + ", best_right=" + best_right + ", i2=" + i2); 

       if(i2 >= i) { 
        left = right = i; 
        plen = 1; 
        // System.out.println("plen=" + plen + ", right=" + right + ", left=" + left); 
       } else if(plenOddArr[i2] < plen_best) { 
        plen = plenOddArr[i2]; 
        do_loop = false; 
        left = right = 0; // Avoid warnings 
        // System.out.println("use mirror image plenArr[i2]=" + plenArr[i2]); 
       } else { 
        plen = plen_best; 
        right = best_right; 
        left = (i - dist_to_best_right + N) % N; 
        // System.out.println("start from plen=" + plen + ", right=" + right + ", left=" + left); 
       } 
      } 

      // Find maximum odd palindrome with center character at i 
      for(; plen < N-1 && do_loop; plen += 2) { 
       char expandleft = sArr[(left - 1 + N) % N]; 
       char expandright = sArr[(right + 1) % N]; 
       if(expandleft == expandright) { 
        left = (left - 1 + N) % N; 
        right = (right + 1) % N; 
       } else 
        break; 
      } 
      plenOddArr[i] = plen; 

      // Keep track of best 
      if(plen > best_plen) { 
       best_right = right; 
       best_left = left; 
       best_plen = plen; 
      } 
     } 

     long tOddNS = threadMXBean.getCurrentThreadCpuTime(); 

     // ******************************************** 
     // Part 3 : Find maximum palindrome for Sk 
     // ******************************************** 
     for(int i=0; i<N; i++) 
      lengths[i] = 1; 

     for(int i=0; i<N; i++) { 
      int plenEven = plenEvenArr[i]; 
      if(plenEven > 1) { 
       for(int k=0; k<N; k++) { 
        // Calculate length of the palindrome in Sk 
        int spaceLeft = (i >= k) ? (i - k) : (N + i - k); 
        int spaceRight = (i > k) ? (N + k - i) : (k - i); 

        // Corner case: i=k and plen=N 
        int len; 
        if(i==k && plenEven == N) 
         len = plenEven; 
        else 
         len = Math.min(plenEven, Math.min(spaceLeft*2, spaceRight*2)); 

        // Update array 
        lengths[k] = Math.max(lengths[k], len);      
       } 
      }   
     } 

     for(int i=0; i<N; i++) { 
      int plenOdd = plenOddArr[i]; 
      if(plenOdd > 1) { 
       for(int k=0; k<N; k++) { 
        // Calculate length of the palindrome in Sk 
        int spaceLeft = (i >= k) ? (i - k) : (N + i - k); 
        int spaceRight = (i >= k) ? (N + k - i - 1) : (k - i - 1); 
        int len = Math.min(plenOdd, Math.min(spaceLeft*2+1, spaceRight*2+1)); 

        // Update array 
        lengths[k] = Math.max(lengths[k], len); 
       } 
      } 
     } 

     // End timer 
     long tEndNS = threadMXBean.getCurrentThreadCpuTime(); 
     System.out.println("Clock stopped"); 

     // Print result   
     for(int i=0; i<N; i++) { 
      System.out.println(lengths[i]); 
     } 

     // Read solution from file 
     int[] solution = new int[N]; 
     System.out.println("Reading solution file " + solutionFile); 
     File solfile = new File(solutionFile); 
     try { 
      BufferedReader solin = new BufferedReader(new InputStreamReader(new FileInputStream(solfile))); 
      for(int i=0; i<N; i++) { 
       solution[i] = Integer.valueOf(solin.readLine()); 
      } 
      solin.close(); 
     } catch(IOException e) { 
      e.printStackTrace(); 
      return; 
     } 

     // Check solution correctness 
     boolean correct = true; 
     for(int i=0; i<N; i++) { 
      if(lengths[i] != solution[i]) { 
       System.out.println(String.format("Mismatch to solution: lengths[%d] = %d (should be %d)", i, lengths[i], solution[i])); 
       correct = false; 
      } 
     } 
     if(correct) 
      System.out.println("Solution is correct"); 

     // Calculate/print total elapsed time 
     System.out.println(String.format("Total CPU time : %.6f sec", (float)(tEndNS - tStartNS)/1.0e9)); 
     System.out.println(String.format(" Even palindromes took %.6f sec", (float)(tEvenNS - tStartNS)/1.0e9)); 
     System.out.println(String.format(" Odd palindromes took %.6f sec", (float)(tOddNS - tEvenNS)/1.0e9)); 
     System.out.println(String.format(" Length calculation took %.6f sec", (float)(tEndNS - tOddNS)/1.0e9)); 
    } 
}

它的工作原理確定，但速度還不夠快。以下是「use_manacher = true」和HackerRank輸入文件 input16.txt的結果，這是一個複雜的測試用例，其中包含近10個字符。

Solution is correct 
Total CPU time : 79.841313 sec 
    Even palindromes took 18.220917 sec 
    Odd palindromes took 16.738907 sec 
    Length calculation took 44.881486 sec

「解決方案正確」是指輸出與HackerRank提供的輸出相匹配。使用「use_manacher = false」，以便它回退到一個簡單的O（n ）算法，我們從每個可能的中心點開始，向兩側展開直到達到字符串的長度：

Total CPU time : 85.582152 sec 
    Even palindromes took 20.451731 sec 
    Odd palindromes took 20.389331 sec 
    Length calculation took 44.741087 sec

最讓我感到意外的是，使用Manacher算法進行優化在循環語境中沒有太多幫助（僅限於10-20％的增益）。此外，找到循環陣列（約35秒）的迴文花費的時間要比將它們映射到旋轉字符串的長度（〜45秒）要少。

目前有超過100個HackerRank滿分，我認爲這意味着應該有一個典型的CPU :)

來源

2016-07-29 Darsen Lu

偉大的問題！工作代碼可能應該遷移到我們的姊妹網站http://codereview.stackexchange.com/。 – rajah9

難道你不能擺脫內部循環的％操作，這是耗時的？ –

你絕對不能在你的第3部分中每次迭代N次（總數爲N^2）的雙循環。我想正確的解決方案會涉及一些記憶。 – justhalf

這仍然是很慢的解決了在10秒內相同的問題的解決方案成功提交.. 。我所知道的是不使用遞歸的迴文檢查

即

static boolean isPali(String s) { 
    if (s.length() == 0 || s.length() == 1) 
     return true; 
    if (s.charAt(0) == s.charAt(s.length() - 1)) 
     return isPali(s.substring(1, s.length() - 1)); 
    return false; 
}

這是我的回答：

import java.io.*; 
import java.util.*; 

public class Solution { 

    // I found this on stackoverflow it was about 3 times faster for a test I ran 
    static boolean isPali(String str){ 
     StringBuilder sb = new StringBuilder(str); 
     return str.equals(sb.reverse().toString()); 
    } 

    static int subs(String s){ 
     int max=0; 
     for(int j = 0 ; j < s.length(); j++) { 
      for (int i = 1; i <= s.length() - j; i++) { 
       String sub = s.substring(j, j+i); 
       if(isPali(sub) && sub.length()>max){ 
        max = sub.length(); 
       } 
      } 

     } 
     return max; 
    } 

    static void rotation(int k,String s) { 
     for (int i = 0; i < k; i++) System.out.println(subs(s.substring(i, k) +s.substring(0, i))); 
    } 


    public static void main(String args[]) { 
     Scanner in = new Scanner(System.in); 
     int k = in.nextInt(); 
     String s = in.next(); 
     rotation(k,s); 
    } 
}

來源

2016-07-29 23:05:11

這是一個更簡單的解決方案！ –

除此之外，您可以避免調用您的迴文方法，其中子字符串大小小於2. 您使用的子字符串函數提供所有可能的子字符串，包括單個字符子字符串。例如，如果你考慮字符串「abba」。對於這個字符串的函數將下面給你10子：

一個，AB，ABB，ABBA，b，BB，BBA，b，BA，一個

，而不是調用所有這10個子字符串的迴文函數，只能爲長度> = 2個字符的子字符串調用迴文函數。這樣你將避免回叫回文功能4次。想象一下，如果您有10^5個字符的字符串。然後你會減少10^5回覆迴文功能。我希望這對你有用。

來源

2016-08-23 12:09:13

Circular Palindromes

回答

相關問題