Türkçe

Her kelimedeki uzunluğu 4 ve bunun katlarında olan palindromları \(O(n^2)\)'de bulabiliriz. Bunun için kelimenin her 4 uzunluğundaki parçası için şu mantığı uygulayabiliriz. Kelimeye \(W\) diyelim ve uzunluğunu her zaman K kabul edelim.

1. Eğer \(W[1]\) ile \(W[K]\) ve \(W[2]\) ile \(W[K-1]\) eşitse bu kelime palindromdur.

   • İlk durumda 4 harf olduğu için, zaten tüm kelimeyi kontrol ederiz ve polindrom olduğunu biliriz.
   • Daha sonra da bu 4 harfi kapsayan kelimelerin baştaki iki harfi ve sondaki iki harfi dışında polindrom olduğunu bildiğimiz için bu harfleri kontrol etmemiz yeterli olur.
   • Örneğin ilk adımda aldığımız kelime "abba" olsun, daha sonra sağına ve soluna ikişer harf ekleyip oluşan yeni kelimenin ilk iki ve son iki harfini kontrol edebiliriz. Eğer harfleri ekledikten sonra oluşan kelime "cdabbadc" ise, ilk ve son iki harfe bakarak palindrom olduğundan emin olabiliriz, çünkü içerdeki kısmın zaten palindrom olduğunu biliyorduk.

2. Bu palindrom'un iki ayrı palindromun birleşiminden olup olmadığını kontrol etmemiz de gerekiyor. Eğer böyleyse bu kelime \(ww^Rww^R\) formatına uyuyordur.

   • Eğer bu şekilde bi kelime değilse daha fazla ilerlememize gerek yok, çünkü bu parça palindrom değilse sağına ve soluna harf eklememiz durumda yeni oluşacak kelime parçasının polindrom olması söz konusu değil.
   • Eğer kelime şu ana kadar bulduğumuz en uzun \(ww^Rww^R\) palindrom ise cevabı bu kelimenin uzunluğuna eşitleriz.

3. Kelime parçasının sağına ve soluna eğer ekleyebiliyorsak 2'şer harf daha ekleriz, ve yine 1. adıma döneriz.

Bunun sonucunda kelimede tüm polindromları kontrol edip, ayrıca hepsinin \(ww^Rww^R\) formatına uyup uymadığına bakmış oluruz.

English

We can find the palindromes that have a length 4 (or a multiple of 4) in every word with the complexity \(O(n^2)\). We can apply this method for every part of the word that has length 4:

Let's name this word \(W\) and assume that it will have a length \(K\).

1. If \(W[1]\) and \(W[K]\) are identical and \(W[2]\) and \(W[K-1]\) are identical, we can say that this word is a palindrome.

   • In the first case, there will be 4 letters in the word and checking these conditions will be sufficient to say the word is a palindrome.
   • Now we add two letters to the beginning and two letters to the end of the word. We just need to check the first and last 2 letters, because we already know that the inside part is a palindrome.
   • For instance, if the word from the first step is "abba", we will add 2 letters to the end and to the beginning of it. In our newly formed word, we are just concerned with the first and last 2 letters as we're already sure that the rest is palindromic.

2. After the first occurrence, we need to check this palindrome is formed with the concatenation of two palindrome words. If so, the word is in the expected format, \(ww^Rww^R\).

   • If the word is not in this format, we should not proceed because there is no way we can make it palindromic by adding 2 letters to the beginning and the end.
   • If the word's length is greater than our current maximum, we will consider its length as our maximum from this point on.

3. We add 2 more letters from the right and left (if we can) and proceed with the first step.

This way, we will check all the palindromes and whether they are in the \(ww^Rww^R\) form or not.

Örnek Çözüm / Sample Solution

#include <stdio.h>
#include <string.h>
char nara[5000], x;
int checker(int ilk, int son)
{
    int a=ilk;
    int b=(ilk+son)/2+1;
    if((b-a)%2 == 1 )
        return 0;
    for(;b!=son+1;a++,b++)
    {
        if(nara[a]!=nara[b])
            return 0;
    }
    return 1;
}
int controller()
{
    int ilk=0,son=1,anlikIlk,anlikSon;
    int key=0,answer=0;
    if(strlen(nara) >= 4)
    for( ; son!=strlen(nara) ;ilk++, son++)
    {
        for(anlikIlk=ilk, anlikSon=son; anlikIlk > -1 && anlikSon < strlen(nara) ; anlikIlk--,anlikSon++)
        {
            if(checker(anlikIlk,anlikSon))
            {
                key = anlikSon-anlikIlk+1;
                if(key>answer)
                    answer=key;
            }
            if(nara[anlikIlk] != nara[anlikSon])
                break;
        }
    }
    return answer;
}

int main()
{
    int naraSayisi,a;

    int i,j;
    scanf("%d\n", &naraSayisi);
    for(i=1 ; i<=naraSayisi ; i++)
    {
        memset(nara,0,strlen(nara));
        for(j=0;;j++)
        {
            scanf("%c", &x);
            if(x=='\n')
                break;
            else
                nara[j]=x;
        }
        a=controller();
    //  if(a%4 == 0)
            printf("%d\n",a);
    //  else
    //      printf("0\n");

    }
}