Circular Palindrome

Question

Ich habe versucht, das Problem der kreisförmigen Palindrom den ganzen Tag, als Teil einer HackerRank challenge zu lösen.

Das traditionelle Palindrom-Problem besteht im Wesentlichen darin, die Länge der längsten symmetrischen Teilstrings (Palindrome) innerhalb eines größeren Strings zu finden. In diesem hackerRank challenge hat die größere Zeichenfolge eine Längenbeschränkung von 10 . Es fügt auch eine weitere Ebene der Komplexität hinzu, indem es nach den Längen für jede Rotationskette fragt.

Eine ähnliche Frage wurde geschrieben here, aber ich konnte nicht genug Informationen extrahieren, um meinen Code schnell genug zu arbeiten.

Ich habe den folgenden Java-Code geschrieben, das eine Modifikation der Manacher's algorithm in einem gedrehten Kontext ist:

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

Es funktioniert OK, aber nicht schnell genug. Hier sind die Ergebnisse mit "use_manager = true" und HackerRank Eingabedatei input16.txt, die ein komplexer Testfall mit fast 10 Zeichen ist.

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 

"Lösung ist korrekt" bedeutet, dass die Ausgabe mit der von HackerRank bereitgestellten übereinstimmt. Mit "use_manacher = false", so dass es auf einen einfachen O (n) Algorithmus zurückgeht, wo wir von jedem möglichen Mittelpunkt aus beginnen und nach beiden Seiten expandieren, bis wir die Länge der Zeichenfolge erreichen, die wir haben:

Was mich am meisten überrascht ist, dass die Optimierung mit Manachers Algorithmus nicht zu viel in einem kreisförmigen Kontext half (nur 10-20% Gewinn). Auch das Finden der Palindrome in einem kreisförmigen Array (~ 35 Sekunden) dauerte weniger Zeit als das Mapping auf Längen in gedrehten Strings (~ 45 Sekunden).

Es gibt mehr als 100 erfolgreiche Einreichungen mit perfekter Punktzahl auf HackerRank, was meiner Meinung nach bedeutet, soll es eine Lösung sein, die das gleiche Problem innerhalb von 10 Sekunden auf einer typische CPU löst :)

Answer 1

Dies ist immer noch sehr langsam .. . ich weiß nur, DONT

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

Das war meine Antwort rekursive Palindrom Check

dh verwenden:

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

Zusätzlich können Sie vermeiden, Ihre palindrome-Methode aufzurufen, wenn die Teilstring-Größe kleiner als 2 ist. Die Teilstring-Funktion, die Sie verwenden, enthält alle möglichen Teilstrings einen einzelnen Zeichenteilstring. Zum Beispiel, wenn Sie die Zeichenfolge "abba" betrachten. Für diese Zeichenfolge wird Ihre Funktion, die Sie unter 10 Teil geben:

ein, ab, abb, abba, b, bb, BBA, b, ba, ein

Statt Aufruf Palindrom-Funktion für alle diese 10 Teilstrings, sollten Sie die Palindrome-Funktion nur für diejenigen Teilstrings aufrufen, deren Länge> = 2 Zeichen. Auf diese Weise vermeiden Sie viermal die Palindrome-Funktion aufzurufen. Stellen Sie sich vor, Sie hätten eine Zeichenfolge von 10^5 Zeichen. Dann werden Sie 10^5 Aufrufe der Palindrom-Funktion reduzieren. Ich hoffe, das ist nützlich für dich.