Circular Palindromes

Question

Я пытаюсь решить проблему кругового палиндрома весь день, как часть HackerRank challenge.

Традиционная проблема палиндрома заключается в том, чтобы найти длину самых длинных симметричных подстрок (палиндромов) внутри большей струны. В этом 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 

Что меня больше всего удивляет, так это то, что оптимизация с помощью алгоритма Манахера не слишком помогла в круговом контексте (только 10-20%). Кроме того, поиск палиндромов в круговой матрице (~ 35 секунд) занимал меньше времени, чем сопоставление их с длинами во вращающихся струнах (~ 45 секунд).

Есть более 100 успешных представлений с совершенным счетом на HackerRank, который я думаю, означает, что должно быть решение, которое решает ту же проблему в течение 10 секунд на обычном процессоре :)

Answer 1

Это по-прежнему очень медленно .. . все, что я знаю не использовать рекурсивную проверку палиндром

т.е.

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); 
    } 
} 

Answer 2

В дополнение к этому вы можете избежать вызова своего метода палиндрома, где размер подстроки меньше 2. Подстрочная функция, которую вы используете, дает все возможные подстроки, включая одну подстроку символов. Например, если вы считаете строку «abba». Для этой строки ваша функция даст вам меньше 10 подстрок:

, аб, АВВ, авва, б, бб, BBA, б, ба,

Вместо вызова palindrome для всех этих подстрок 10, вы должны вызвать функцию палиндрома только для тех подстрок, длина которых> = 2 символа. Таким образом, вы избежите вызова функции палиндрома 4 раза. Представьте, если у вас есть строка из 10^5 символов. Затем вы уменьшите 10^5 звонков на функцию палиндрома. Надеюсь, это полезно для вас.