24ος ΠΔΠ Γ' Φάση: Παλίνδρομο (minpali) - Λύση

Επεξήγηση εκφώνησης

Μας ζητείται να υπολογίσουμε το μικρότερο μήκος παλίνδρομου που μπορεί να παραχθεί έχοντας ως prefix τη δοσμένη συμβολοσειρά. Με άλλα λόγια, πρέπει να προσθέσουμε όσο το δυνατόν λιγότερους χαρακτήρες στο τέλος της συμβολοσειράς εισόδου, ώστε να πάρουμε παλίνδρομο.

Λόγω της φύσεως των παλίνδρομων, θα χρειαστεί πολλές φορές να αναφερθούμε σε κάποια αντεστραμμένη συμβολοσειρά. Θα γράφουμε \(S[i\ldots j]\) για να αναφερθούμε στη συμβολοσειρά μεταξύ των θέσεων \(i\) και \(j\) \((1\le i \le j \le N)\). Αντίστοιχα, θα γράφουμε \(\overleftarrow{S}[i\ldots j]\) για να αναφερθούμε στην αντεστραμμένη συμβολοσειρά μεταξύ των θέσεων \(i\) και \(j\). Έτσι αν \(S=abcd\), τότε \(S[2\ldots 3]=bc\) και \(\overleftarrow{S}[2\ldots 3]=cb\).

Ας προδώσουμε εξαρχής τη βασική ιδέα που ακολουθούν όλες οι προτεινόμενες λύσεις. Αρκεί να βρούμε ένα επίθεμα της συμβολοσειράς μας που να είναι παλινδρομικό. Αυτό μας αρκεί, διότι μετά μπορούμε να πάρουμε όσους χαρακτήρες περίσσεψαν από την αρχή της συμβολοσειράς (πρόθεμα), να τους αντιστρέψουμε, και να τους προσθέσουμε στο τέλος της συμβολοσειράς μας. Το αποτέλεσμα θα είναι παλίνδρομο ¹.

Για παράδειγμα, αν έχουμε τη συμβολοσειρά cababa τότε ένα παλινδρομικό επίθεμα είναι το ababa. Έτσι σχηματίζουμε το παλίνδρομο cababac. Βεβαίως είναι παλιδρομικό επίθεμα και το aba που θα έδινε τη συμβολοσειρά cabababac. Επίσης μόνο του το τελευταίο γράμμα a είναι παλίνδρομο, και θα έδινε τη συμβολοσειρά cababababac.

Προφανώς για να προσθέσουμε τους ελάχιστους χαρακτήρες, πρέπει το πρόθεμα που θα περισσέψει να είναι όσο το δυνατόν μικρότερο. Συνεπώς η λύση μας ανάγεται στην εύρεση του μέγιστου παλινδρομικού επιθέματος.

Δώστε τρία λεπτά να καταλάβετε γιατί αυτό μας αρκεί, καθώς ό,τι ακολουθεί από εδώ και πέρα είναι απλώς τεχνικές λεπτομέρειες.

Αργή λύση \(\mathcal{O}(N^2)\) Brute Force

Ψάχνουμε το μέγιστο παλινδρομικό επίθεμα. Μπορούμε να δοκιμάσουμε κάθε θέση \(i\) και να ελέγχουμε αν το \(S[i\ldots N]\) είναι παλίνδρομο. Αυτό σημαίνει ότι πρέπει \(S[i\ldots N] = \overleftarrow{S}[i\ldots N]\).

Αφού κάνουμε \(N\) ελέγχους παλινδρομικού επιθέματος, και κάθε ένας παίρνει χρόνο \(\mathcal{O}(N)\), η τελική πολυπλοκότητα είναι \(\mathcal{O}(N^2)\).

Παρακάτω δίνεται μία ενδεικτική υλοποίηση αυτής της λύσης. Η λύση αυτή περνά τα 11 από τα 14 test cases.

#include <bits/stdc++.h>

using namespace std;

const long MAXN = long(1e7);
long N;
char S[MAXN+5];

bool is_palindrome(long from){
  //check if S[from...N] is a palindrome
  //that is, if S[from...N] == reverse(S)[from...N]
  for(int i=0; i<=(N-from); ++i)
    if (S[from+i] != S[N-i]) return false;
  return true;
}

int main(){
#ifdef CONTEST
  freopen("minpali.in","r",stdin);  
  freopen("minpali.out","w",stdout);
#endif

  long from;
  scanf("%ld %s",&N,S+1); //Writing S+1 puts the first character in index 1 instead of 0
  for(from=1; from<=N && !is_palindrome(from); ++from)
    ;
  long maxPalindromicSuffix = N-from+1;
  printf("%ld\n",2*N-maxPalindromicSuffix);
  return 0;
}

Βέλτιστες λύσεις - \(\mathcal{O}(N)\)

Όπως είδαμε και στη Brute Force, αρκεί να γίνουν γρήγορα οι έλεγχοι

για κάθε \(i\) από \(1\) έως \(N\). Αυτό μπορούμε να το πετύχουμε με διάφορους τρόπους, όπως με Rabin Karp, με \(\mathcal{Z}\)-Algorithm ή με KMP, αρκεί να τους τροποποιήσουμε κατάλληλα.

Τέλος, μία βέλτιστη λύση προκύπτει άμεσα από τον αλγόριθμο του Manacher, ο οποίος είναι ένας αλγόριθμος που βρίσκει εφαρμογές σε προβλήματα σχετικά με παλίνδρομα (πχ πλήθος παλινδρόμων, μέγιστο παλίνδρομο, μέγιστο παλινδρομικό επίθεμα, και άλλα). Παρότι ταιριάζει άψογα σε αυτή την περίπτωση, τον αναφέρουμε τελευταίο γιατί οι υπόλοιποι αλγόριθμοι βρίσκουν πολύ περισσότερες εφαρμογές, όχι μόνο σε προβλήματα που σχετίζονται με παλίνδρομα.

Βέλτιστη λύση με \(\mathcal{Z}\)-Algorithm - \(\mathcal{O}(N)\)

Γνώσεις που θα χρειαστούμε: \(\mathcal{Z}\) algorithm
(Z algorithm)

Έστω ότι έχουμε τη συμβολοσειρά ababaccababa. Δημιουργούμε τον παρακάτω πίνακα

Στην ουσία, για κάθε θέση φανταζόμαστε τη συμβολοσειρά που αρχίζει από αυτή τη θέση και τελειώνει στο τέλος. Στον πίνακα συμπληρώνουμε το μέγιστο κοινό πρόθεμα της συμβολοσειράς αυτής με την αρχική μας συμβολοσειρά. Ο αλγόριθμος \(\mathcal{Z}\) μας δίνει ακριβώς αυτό τον πίνακα σε γραμμικό χρόνο ².

Θέλουμε να βρούμε ένα παλίνδρομο από μια θέση \(i\) έως το τέλος της συμβολοσειράς εισόδου (όπως εξηγήσαμε αρχικά). Έστω ότι η είσοδος είναι η συμβολοσειρά cababa. Φτιάχνουμε έναν πίνακα χαρακτήρων \(T\) με μήκος \(2Ν\). Αντιστρέφουμε τη συμβολοσειρά εισόδου στο πρώτο μισό του πίνακα χαρακτήρων \(T\) και στο δεύτερο μισό του πίνακα έχουμε αυτούσια τη συμβολοσειρά εισόδου. Κατόπιν τρέχουμε τον αλγόριθμο \(\mathcal{Z}\) σε αυτή τη συμβολοσειρά (ababaccababa). Το αποτέλεσμα για το συγκεκριμένο παράδειγμα είναι ο παραπάνω πίνακας.

Υποστηρίζουμε ότι η έξοδός του είναι αρκετή για να κάνουμε όλους τους ελέγχους που χρειαζόμαστε. Προσπαθήστε τρία λεπτά να φανταστείτε μόνοι σας γιατί αυτό ισχύει.

Στο παράδειγμά μας, αν θέλαμε να ελέγξουμε αν \(S[2\ldots6] =ababa\) είναι ίσο με το \(\overleftarrow{S}[2\ldots 6] =ababa\) (το οποίο με το μάτι βλέπουμε ότι ισχύει) θα κοιτούσαμε απλώς την έξοδο του \(\mathcal{Z}\) αλγόριθμου που αντιστοιχεί στην αρχική θέση \(2\), δηλαδή την \(T[6+2]=T[8]\). Εφόσον η απάντηση είναι \(5\), και οι συμβολοσειρές που θέλουμε να ελέγξουμε έχουν μήκος \(6-2+1=5\), άρα πράγματι είναι ίσες και το \(S[2\ldots 6]\) είναι παλινδρομικό επίθεμα.

Με τον ίδιο έλεγχο βλέπουμε ότι είναι παλινδρομικό επίθεμα το \(S[4\ldots 6]\) και το \(S[6\ldots 6]\), αλλά όχι τα \(S[1\ldots 6], S[3\ldots 6]\) και \(S[5\ldots 6]\).

Ο λόγος που αυτός ο έλεγχος είναι αρκετός, είναι ότι από ορισμού του ο αλγόριθμός μας συγκρίνει πόσο μοιάζει το \(T[1\ldots 2N]\) με το \(T[N+i\ldots 2N]\). Όμως από κατασκευής του \(T\) έχουμε ότι \(T[N+i\ldots 2N] == S[i\ldots N]\), και \(T[1\ldots] = \overleftarrow{S}[N\ldots]\). Συνεπώς ελέγχουμε ακριβώς αυτό που χρειαζόμασταν.

Μία ενδεικτική υλοποίηση με \(\mathcal{Z}\)-algorithm παρουσιάζεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;

const long MAXN = long(1e7);
long N, Z[2*MAXN+5];
char T[2*MAXN+5];

void fill_Z(const char *s, long *Z, long n) { 
   long L, R, k; 
   L = R = 1;
   Z[1] = n;
   
   for(long i = 2; i <= n; ++i) {
      long k = i-L+1;
      if(i > R || Z[k] >= R-i){ 
         L = i;
         R = max(R,i);
         while (R<=n && s[R-L+1]==s[R]) R++; 
         Z[i] = R-L; 
         R--; 
      } else { 
         Z[i] = Z[k]; 
      } 
   } 
} 

int main(){
#ifdef CONTEST
   freopen("minpali.in","r",stdin);
   freopen("minpali.out","w",stdout);
#endif
   scanf("%ld",&N);
   scanf(" %s",T+N+1);//read string from middle of string array
   //add reversed string in the yet unfilled first half
   for(long i=1;i<=N;i++)
      T[i] = T[2*N-i+1];
   fill_Z(T,Z,2*N);

   long maxPalindromicSuffix;
   for(long i=N+1; i<=2*N; ++i){
      if(Z[i] >= 2*N-i+1){
         maxPalindromicSuffix = 2*N-i+1;
         break;
      }
   }
   
   printf("%ld\n",2*N-maxPalindromicSuffix);
   return 0;
}

Βέλτιστη λύση με KMP - \(\mathcal{O}(N)\)

Γνώσεις που θα χρειαστούμε: Knuth-Morris-Pratt (KMP) algorithm
(camp ΠΔΠ 2017 KMP explained)
(CP-Algorithms KMP)

Ο αλγόριθμος KMP είναι ο πιο γνωστός αλγόριθμος για Pattern Matching. Δηλαδή δοθέντων δύο συμβολοσειρών, βρίσκει τις εμφανίσεις της δεύτερης μέσα στην πρώτη. Τονίζουμε ότι δεν είναι ο πιο κατανοητός αλγόριθμος, και αγνοούμε γιατί είναι ο πιο γνωστός. Ο αλγόριθμος \(\mathcal{Z}\) μπορεί να λύσει το ίδιο ακριβώς πρόβλημα και είναι απείρως κατανοητότερος. Όμως για λόγους πληρότητας, παραθέτουμε και αυτή τη λύση.

Έστω ότι έχουμε τη συμβολοσειρά ababaccababa. Δημιουργούμε τον παρακάτω πίνακα

Στην ουσία, για κάθε θέση φανταζόμαστε τη συμβολοσειρά που τελειώνει σε αυτή τη θέση (δηλαδή για τη θέση \(i\), φανταζόμαστε τη συμβολοσειρά \(S[1\ldots i\)]). Στον πίνακα συμπληρώνουμε το μήκος της μέγιστης δυνατής συμβολοσειράς που είναι ταυτόχρονα και πρόθεμα και επίθεμα της \(S[1\ldots i]\), χωρίς βέβαια να είναι η ίδια η \(S[1\ldots i]\). Για παράδειγμα, για \(i=5\) ψάχνουμε τη μέγιστη συμβολοσειρά που είναι και πρόθεμα και επίθεμα της συμβολοσειράς ababa. Αυτή είναι η aba που έχει μήκος \(3\), κι επομένως \(F[5]=3\). Ο αλγόριθμος KMP μας επιστρέφει τον πίνακα \(F\) σε γραμμικό χρόνο.

Το τρικ που θα κάνουμε είναι εντελώς όμοιο με αυτό του \(\mathcal{Z}\). Έστω ότι η είσοδος είναι η συμβολοσειρά cababa. Φτιάχνουμε έναν πίνακα χαρακτήρων \(T\) με μήκος \(2Ν\). Αντιστρέφουμε τη συμβολοσειρά εισόδου στο πρώτο μισό του πίνακα χαρακτήρων \(T\) και στο δεύτερο μισό του πίνακα έχουμε αυτούσια τη συμβολοσειρά εισόδου. Κατόπιν τρέχουμε βρίσκουμε τον πίνακα \(F\) για αυτή τη συμβολοσειρά (ababaccababa). Το αποτέλεσμα για το συγκεκριμένο παράδειγμα είναι ο παραπάνω πίνακας.

Υποστηρίζουμε ότι ο αριθμός στην τελευταία θέση του πίνακα \(F\) είναι ακριβώς το μήκος του μέγιστου παλινδρομικού επιθέματος. Η μόνη εξαίρεση είναι αν είναι μεγαλύτερος από το \(N\), που τότε έχουμε ότι η αρχική λέξη ήταν ήδη παλίνδρομο. Προσπαθήστε \(3\) λεπτά να το αποδείξετε μόνοι σας.

Ας υποθέσουμε ότι ο αριθμός στην τελευταία θέση του πίνακα \(F\) είναι μικρότερος του \(N\) (αλλιώς η απόδειξη είναι πολύ εύκολη και αφήνεται στον αναγνώστη). Τότε το μέγιστο επίθεμα της λέξης \(T\) αντιστοιχεί σε επίθεμα της λέξης \(S\), λόγω του τρόπου που κατασκευάσαμε την \(T\). Επίσης το πρόθεμα της \(T\) αντιστοιχεί σε αντεστραμμένο επίθεμα του \(S\), κι άρα η θέση \(F[N]\) περιλαμβάνει ένα παλινδρομικό επίθεμα της \(S\). Για να δούμε ότι είναι πράγματι το μέγιστο, δουλεύουμε με απαγωγή εις άτοπο. Υποθέτουμε ότι υπάρχει ένα ακόμα μεγαλύτερο παλινδρομικό επίθεμα, και βλέπουμε ότι τότε το \(F[5]\) θα έπρεπε να είναι μεγαλύτερο από την παρούσα τιμή του.

Μία ενδεικτική υλοποίηση με KMP παρουσιάζεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;
const long MAXC = 10000000;

long N, F[2*MAXC+5];
char T[2*MAXC+5];

void Prefix () {
  long i, j;
  F[0] = F[1] = 0;
  for ( i=2; i<=2*N; ++i ) {
    j = F[i-1];
    while ( 1 ) {
      if ( T[i] == T[j+1] ) {
	F[i] = j+1;
	break;
      }
      else if ( j==0 ) {
	F[i] = j;
	break;
      }
      else {
	j = F[j];
      }
    }
  }
}

int main () {
#ifdef CONTEST
  freopen ("minpali.in","r",stdin);
  freopen ("minpali.out", "w", stdout );
#endif
  scanf ("%ld", &N);
  scanf (" %s", T+N+1); //put the word in the second half of T
  //reverse the word
  for ( long i=1; i<=N; ++i )
    T[i] = T[2*N-i+1];
  Prefix();
  printf("%ld\n", 2*N-min(N,F[2*N]));
  return 0;
}

Βέλτιστη Λύση με Rabin Karp - \(\mathcal{O}(N)\)

Γνώσεις που θα χρειαστούμε: Rabin-Karp Algorithm και Rolling hash
(Κώδικας από camp ΠΔΠ 2017 Rabin-Karp)
(Διαφάνειες από camp ΠΔΠ 2017 Rabin-Karp (προς το τέλος του pdf))
(Καλλίνικος Hash-Table)
(wikipedia Rabin-Karp)
(wikipedia Rolling hash)

Υπενθυμίζουμε ότι πρέπει να κάνουμε γρήγορα τους ελέγχους \(S[i\ldots N] == \overleftarrow{S}[i \ldots N]\), για κάθε \(i\). Στη λύση που ακολουθεί θα χρησιμοποιήσουμε τον αλγόριθμο Rabin-Karp. Η ιδέα είναι ότι ο αλγόριθμος ‘μεταμορφώνει’ την κάθε συμβολοσειρά σε έναν ακέραιο αριθμό (hash), ώστε αντί να ξοδεύουμε πολύ χρόνο για τον έλεγχο ισότητας δύο συμβολοσειρών, να ξοδεύουμε \(\mathcal{O}(1)\) χρόνο για τον έλεγχο των αντίστοιχων μεταμορφωμένων hash.

Προσοχή: Στην εκφώνηση δεν δίνεται το σύνολο χαρακτήρων που περιέχει η συμβολοσειρά. Έτσι δε μπορούμε να υποθέσουμε ότι έχουμε μόνο το αγγλικό αλφάβητο (\(26\) γράμματα). Θα πρέπει να υποθέσουμε ότι είναι πιθανοί και οι \(256\) χαρακτήρες που παρέχει η C++.

Η δημιουργία των hash για τις συμβολοσειρές \(\overleftarrow{S}[i\ldots N]\) γίνεται με το γνωστό τρόπο, απλώς από δεξιά προς τα αριστερά. Αρχικά δημιουργούμε το hash της \(\overleftarrow{S}[N\ldots N]\), το οποίο είναι απλά η ακέραια τιμή του τελευταίου χαρακτήρα (κάθε χαρακτήρας αντιστοιχεί σε έναν ακέραιο αριθμό, σύμφωνα με τον πίνακα ASCII). Για να βρούμε το επόμενο hash, δηλαδή αυτό της συμβολοσειράς \(\overleftarrow{S}[N-1\ldots N]\), απλώς πολλαπλασιάζουμε το παλιό hash με \(256\) και προσθέτουμε τον επόμενο χαρακτήρα. Συνεχίζουμε με τον ίδιο τρόπο και για τις υπόλοιπες τιμές.

Η δημιουργία των hash για τις συμβολοσειρές \(S[i\ldots N]\) είναι κάτι καινούργιο. Αυτό διότι συνήθως προσθέτουμε ένα γράμμα στο τέλος της συμβολοσειράς μας, ενώ στη συγκεκριμένη περίπτωση το προσθέτουμε στην αρχή της. Κινούμαστε και πάλι από τα δεξιά προς τα αριστερά. Κοιτώντας τον ορισμό της hash τιμής, το πρώτο γράμμα πολλαπλασιάζεται με \(256^{l-1}\), όπου \(l\) το μέγεθος της συμβολοσειράς που μας ενδιαφέρει. Στην περίπτωσή μας \(l = N-i+1\), που σημαίνει ότι το πρώτο γράμμα το πολλαπλασιάζουμε με \(256^{N-i}\).

Πολυπλοκότητα της λύσης: \(\mathcal{O}(N)\), αφού κάθε χαρακτήρας χρησιμοποιείται δύο φορές. Η λύση αυτή περνά όλα τα test cases.

Μία ενδεικτική υλοποίηση με τη χρήση Rabin-Karp Algorithm παρουσιάζεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long hasht;
const hasht MOD = hasht(1e9)+7;   //It is imperative that MOD*MOD fit hasht typedef
const long  MAXN = long(1e7);
const long  C = long(256); //number of characters in C++
long        N;
char        S[MAXN+5];

int main(){
#ifdef CONTEST
   freopen("minpali.in", "r",stdin);
   freopen("minpali.out","w",stdout);
#endif
   scanf("%ld %s",&N,S+1); //S+1 makes our string start from 1 instead of 0
   
   long maxPalindromicSuffix;
   hasht left_right = 0, right_left = 0, expC=1;
   for(long i=N;i>=1;i--){
      left_right = ( left_right + ((S[i]*expC)%MOD) ) % MOD;
      right_left = (((right_left*C)%MOD) + S[i] ) % MOD;
      expC = (expC * C) % MOD;
      if(left_right == right_left){
         maxPalindromicSuffix = N-i+1;
      }
   }
   printf("%ld\n",2*N-maxPalindromicSuffix);
   return 0;
}

Constant Optimization για τον Rabin-Karp

Συχνά οι λύσεις που χρησιμοποιούν Rabin-Karp είναι λίγες φορές πιο αργές από άλλες υλοποιήσεις (πχ από αυτές που χρησιμοποιούν KMP). Για αυτό ευθύνεται η πράξη mod η οποία είναι πολύ αργή, και επίσης κάνει και τον κώδικα πολύ άσχημο. Για το λόγο αυτό παρουσιάζουμε ένα τρόπο να την αποφύγουμε εξ’ ολοκλήρου.

Αντί για υπόλοιπα διαιρέσεων με πρώτο αριθμό που υπολογιστικά έχουν κάποιο βάρος, μπορούμε να χρησιμοποιήσουμε υπόλοιπα με το \(2^{64}\). Γιατί αυτό είναι καλύτερο; Διότι στην πραγματικότητα δε θα κάνουμε ποτέ την πράξη mod. Απλά θα αφήσουμε τους unsigned long long αριθμούς μας να ξεχειλίσουν (overflow)!! Αυτό είναι ακριβώς ισοδύναμο με το υπόλοιπο με το \(2^{64}\).

Το κόστος είναι κάπως μεγαλύτερη αβεβαιότητα. Θυμηθείτε ότι ο Rabin-Karp δε δουλεύει πάντα (λόγω του mod που κάνουμε), αλλά η πιθανότητα αποτυχίας μπορεί να γίνει τόσο μικρή που να είναι αμελητέα. Για παράδειγμα μπορεί να γίνει μικρότερη από την πιθανότητα ακτινοβολία από το διάστημα να έρθει ακριβώς τη λάθος στιγμή και να αλλάξει ένα bit του υπολογιστή σας, κι έτσι να τυπώσετε λάθος αποτέλεσμα ενώ έχετε σωστό αλγόριθμο!!!

Αυτή τη φορά τα πράγματα δεν είναι έτσι. Διότι αυτός που δημιουργεί τα testcases ξέρει κι αυτός το τρικ μας, άρα ξέρει ακριβώς τον αριθμό \(2^{64}\) με τον οποίο “κάνουμε” mod, και μπορεί να δημιουργήσει κακά testcases στα οποία να την πατάμε. Για του λόγου το αληθές, \(3\) από τα \(14\) testcases αυτού του προβλήματος δημιουργήθηκαν ακριβώς έτσι. Συνεπώς χρειαζόμαστε έναν τρόπο να μπερδέψουμε τα testcases, αφού πλέον δε μπορούμε αυτό να το πετύχουμε με τον αριθμό με τον οποίο κάνουμε mod.

Η λύση είναι να παίξουμε λίγο με το πλήθος πιθανών χαρακτήρων. Είναι αλήθεια ότι η \(C++\) παρέχει \(256\) χαρακτήρες, κι έτσι θα ήταν λάθος να βάζαμε αριθμό μικρότερο από \(256\) στο \(C\) (βλέπε κώδικα). Όμως δεν υπάρχει κανένα πρόβλημα να βάλουμε μεγαλύτερη τιμή! Προφανώς πλέον η αβεβαιότητα μας είναι μεγαλύτερη, καθώς η ευκαιρία μας να μπερδέψουμε τα testcases δεν είναι τόσο σημαντική (πχ θα βάλουμε κάτι μεταξύ \(256\) και \(500\), ενώ με το mod είχαμε τη δυνατότητα να βάλουμε οποιονδήποτε τεράστιο αριθμό).

Έτσι δε θα χρησιμοποιήσετε ποτέ αυτό το τρικ σε ιατρικές εφαρμογές. Για τα πλαίσια του διαγωνισμού όμως είναι άψογη, καθώς είναι πιθανότερο να κερδίσετε ένα testcase λόγω καλύτερου χρόνου σε σχέση με τον κλασικό Rabin-Karp, παρά να χάσετε ένα λόγω ατυχίας.

Ακολουθεί η τροποποίηση στην Rabin-Karp λύση, όπου αλλάζει μόνο η σταθερά \(C\) και αφαιρούνται τα mod:

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long hasht;
const long  MAXN = long(1e7);
const long  C = long(256+13); //number of characters in C++, plus something to confuse the testcases
long        N;
char        S[MAXN+5];

int main(){
#ifdef CONTEST
   freopen("minpali.in", "r",stdin);
   freopen("minpali.out","w",stdout);
#endif
   scanf("%ld %s",&N,S+1); //S+1 makes our string start from 1 instead of 0
   
   long maxPalindromicSuffix;
   hasht left_right = 0, right_left = 0, expC=1;
   for(long i=N;i>=1;i--){
      left_right = left_right + expC*S[i];
      right_left = right_left*C + S[i];
      expC = expC * C;
      if(left_right == right_left){
         maxPalindromicSuffix = N-i+1;
      }
   }
   printf("%ld\n",2*N-maxPalindromicSuffix);
   return 0;
}

Βέλτιστη λύση με Manacher - \(\mathcal{O}(N)\)

Γνώσεις που θα χρειαστούμε: Manacher Algorithm
(CP-Algorithms)

Τέλος, αναφέρουμε τη λύση με τον αλγόριθμο Manacher. Προσέχουμε ότι κάθε παλίνδρομο έχει ένα κέντρο. Για παράδειγμα το παλίνδρομο aba έχει κέντρο το γράμμα b, και μήκος \(3\). Το κέντρο αυτό μπορεί και να βρίσκεται ανάμεσα σε δύο γράμματα, όπως στην περίπτωση του παλινδρόμου abba. Ο αλγόριθμος Manacher τρέχει σε γραμμικό χρόνο. Για κάθε υποψήφιο κέντρο, μας επιστρέφει το μέγιστο παλίνδρομο με αυτό το κέντρο. Για παράδειγμα, για τη συμβολοσειρά cababa δημιουργεί τον παρακάτω πίνακα (σημειώνουμε με * τα υποψήφια κέντρα που βρίσκονται ανάμεσα σε δύο γράμματα, τα οποία όμως δεν αντιστοιχούν σε πραγματικούς χαρακτήρες).

Προσέξτε ότι αν ελέγξουμε το κέντρο του μέγιστου παλινδρομικού επιθέματος, θα βρούμε το μήκος του μέγιστου παλινδρομικού επιθέματος. Αυτό ισχύει διότι αποκλείεται εκείνο το κέντρο να είναι κέντρο ακόμα μεγαλύτερου παλινδρόμου, καθώς θα έπρεπε να εκτείνεται μετά το τέλος της συμβολοσειράς εισόδου. Επομένως αρκεί να ελέγξουμε όλα τα παλίνδρομα που μας προτείνει ο πίνακας του αλγορίθμου Manacher, και να κρατήσουμε το μέγιστο από όσα τελειώνουν στο τέλος της συμβολοσειράς εισόδου.

#include <bits/stdc++.h>
using namespace std;
const long MAXC = 10000000;
const char AKIRO = '#';

long P[2*MAXC+5], N;
char str[2*MAXC+5];

void CreateManacherTable() {
  long center=0, mirror, right, j;

  for ( long i=1; i<=2*N+1; ++i ) {
    mirror = center - (i-center);
    if ( mirror > 0 && (mirror - P[mirror] > center - P[center]) ) {
      P[i] = P[mirror];
    }
    else {
      //extend i
      
      //Take the above inequality and make it an equality
      right = max(mirror-center+P[center],(long)1);
      //Since right may be negative ( if i is out of range from center ),
      //we may need to set it to 1
      
      for (j=right; i+j <= 2*N+1 && i-j > 0 && str[i+j] == str[i-j]; ++j );
      --j;

      P[i] = j;
      center = i;
    }
  }
}

int main() {
#ifdef CONTEST
  freopen ("minpali.in","r",stdin);
  freopen ("minpali.out", "w", stdout );
#endif
  scanf ( "%ld %s", &N, str+1 );
  str[2*N+1] = AKIRO;
  for (long i=N; i>=1; --i ) {
    str[2*i] = str[i];
    str[2*i-1] = AKIRO;
  }

  CreateManacherTable();

  long maxPalindromicSuffix;
  for(long i=1; i<=2*N; ++i) {
    //The palindrome is centered at position i/2 (due to our stretching)
    //Its size is P[i], so it extends P[i]/2 positions to the right and P[i]/2 to the left
    //If this palindrome is a suffix, we need i/2+P[i]/2 == N
    if ( i/2 + P[i]/2 == N) {
      maxPalindromicSuffix = P[i];
      break;
    }
  }
  printf("%ld\n", 2*N-maxPalindromicSuffix);
  return 0;
}