31ος ΠΔΠ Γ' Φάση: Συμμετρικές συμβολοσειρές (symstr) - Λύση

Συγγραφέας: Βαγγέλης Κηπουρίδης

Ζητούμενο

Δίνεται ένα κείμενο. Για κάθε θέση του κειμένου θέλουμε να ελέγξουμε αν μετά τη διαγραφή της καταλήγουμε σε ένα συμμετρικό κείμενο. Συμμετρικό λέμε ένα κείμενο του οποίου το πρώτο μισό είναι ίδιο με το δεύτερο. Για παράδειγμα, δοθέντος του κείμενου \(helloAhello\), αφαιρώντας το γράμμα \(A\) καταλήγουμε στο συμμετρικό κείμενο \(hellohello\), που έχει ίδιο πρώτο και δεύτερο μισό (\(hello\)). Αντίθετα, αν αφαιρέσουμε οποιοδήποτε άλλο γράμμα (πχ το πρώτο \(h\)) δεν έχουμε ίδιο πρώτο και δεύτερο μισό (elloA - hello).

Περιπτώσεις

Για να απλοποιήσουμε τη συζήτηση, θα διακρίνουμε τις εξής περιπτώσεις:

Το γράμμα που αφαιρούμε είναι στο πρώτο μισό του κειμένου.
Το γράμμα που αφαιρούμε είναι αυτό ακριβώς στη μέση. Τότε πολύ εύκολα σε γραμμικό χρόνο ελέγχουμε αν τα δύο μισά που απομένουν είναι ίδια.
Το γράμμα που αφαιρούμε είναι στο δεύτερο μισό του κειμένου.

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

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

Λύση

Παρατηρούμε ότι όποιο γράμμα και να αφαιρέσουμε από το δεύτερο μισό του κειμένου, γνωρίζουμε ακριβώς ποιο είναι το πρώτο μισό. Έτσι, στην παρακάτω εικόνα, όποιο γράμμα και να αφαιρέσουμε από τα γκρι, το πρώτο μισό του κειμένου παραμένει το γαλάζιο (\(hello\)).

Ας κάνουμε λοιπόν κάποιες δοκιμές. Έστω ότι αφαιρούμε το \(l\), στη θέση \(8\). Τότε θέλουμε το κείμενο στις θέσεις \(1-2\) να είναι ίδιο με το \(6-7\) (\(he\) και \(he\)) και το κείμενο στις θέσεις \(3-5\) να είναι ίδιο με το \(9-11\) (\(llo\) και \(Alo\)). Στη συγκεκριμένη περίπτωση δεν ισχύει.

Παροιμοίως αν αφαιρέσουμε το \(A\), στη θέση \(9\) θέλουμε το κείμενο στις θέσεις \(1-3\) να είναι ίδιο με το \(6-8\) (\(hel\) και \(hel\)) και το κείμενο στις θέσεις \(4-5\) να είναι ίδιο με το \(10-11\) (\(lo\) και \(lo\)). Στη συγκεκριμένη περίπτωση ισχύει.

Παρατηρούμε ότι όποιο γράμμα και να αφαιρέσουμε από το δεύτερο μισό, χρειάζεται πάντα να απαντήσουμε σε δύο όμοια ερωτήματα:

\(Q_1(x)\): Είναι ίδιο το κείμενο μήκους \(x\) που αρχίζει από τη θέση \(1\) με το κείμενο μήκους \(x\) που αρχίζει από τη θέση \(6\);
\(Q_2(x)\): Είναι ίδιο το κείμενο μήκους \(x\) που τερματίζει στη θέση \(5\) με το κείμενο μήκους \(x\) που τερματίζει στη θέση \(11\);

Ξανά, για ευκολία της συζήτησης, θα σχολιάσουμε μόνο το πρώτο ερώτημα. Αν \(x==1\), τότε ο έλεγχος που πρέπει να κάνουμε είναι πολύ απλός, αρκεί να κοιτάξουμε αν \(str[1]==str[6]\). Γενικά, για να έχει θετική απάντηση το ερώτημα \(Q_1(x)\) θα πρέπει να ισχύουν δύο πράγματα. Και να έχει θετική απάντηση το \(Q_1(x-1)\), και να είναι ίδια τα γράμματα \(str[x]\) και \(str[x+5]\). Με αυτό τον τρόπο μπορούμε να προϋπολογίσουμε σε \(\mathcal{O}(1)\) χρόνο την απάντηση για κάθε ένα από τα ερωτήματα \(Q_1(x)\) και \(Q_2(x)\).

Στο παράδειγμά μας θα είχαμε \(Q_1(1)=Q_1(2)=Q_1(3)=true\) και \(Q_1(4)=Q_1(5)=Q_1(6)=false\). Παρομοίως θα είχαμε \(Q_2(1)=Q_2(2)=true\) και \(Q_2(3)=Q_2(4)=Q_2(5)=Q_2(6)=false\).

Παρακάτω δίνουμε κώδικα που αποτυπώνει την παραπάνω συζήτηση. Η έξοδος του προβλήματος ήταν η παρακάτω: Ζητείται να τυπωθεί \(0\) αν δεν υπάρχει γράμμα που η διαγραφή του να δίνει συμμετρικό κείμενο, ή το πρώτο μισό του συμμετρικού κειμένου, αν μπορούσε να δημιουργηθεί μόνο ένα. Τέλος, αν γίνεται να δημιουργηθούν παραπάνω διαφορετικά συμμετρικά κείμενα, πρέπει να τυπωθεί ο αριθμός \(1\).

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


int t, n;
char word[MAXN +5];
bool Q1left[MAXN +5], Q2left[MAXN +5], Q1right[MAXN +5], Q2right[MAXN+5];

int main()
{
	freopen("symstr.in","r",stdin);
	freopen("symstr.out","w",stdout);
	scanf("%d%d",&t,&n);
	while (t--)
	{
		scanf("%s",word+1);
		bool left, right, middle;
		left = right = false;
		middle = true;
		Q1left[0] = Q1right[0] = Q2left[0] = Q2right[0] = 1;

		//middle knows whether the left and the right part are equal
		//Q1 and Q2 are as described in the solution
		//printf("word: %s\n", word+1);
		for(int i=1; i<=n/2; ++i) {
			Q1left[i] = Q1right[i] = Q2left[i] = Q2right[i] = 0;
			if(word[i] != word[n/2+1+i]) middle = false;
			if(Q1right[i-1] && word[i] == word[n/2+i]) Q1right[i] = 1;
            		if(Q2right[i-1] && word[n/2+1-i] == word[n+1-i]) Q2right[i] = 1;
            		if(Q1left[i-1] && word[i] == word[n/2+1+i]) Q1left[i] = 1;
            		if(Q2left[i-1] && word[n/2+2-i] == word[n+1-i]) Q2left[i] = 1;
		}

		for(int i=1; i<=n/2; ++i) {
			if (Q1left[i-1] && Q2left[n/2-i+1]) left = true;
            		if (Q1right[i] && Q2right[n/2-i]) right = true;
		}

		if (middle) printf("%s\n",word+n/2+2);
		else if (left && right) printf("1\n");
		else if (right) word[n/2+1] = '\0', printf("%s\n",word+1);
		//above is a hack to directly print the left half
		else if (left) printf("%s\n",word+n/2+2);
		else printf("0\n");
	}
}