Submission #223553

#	Time	Username	Problem	Language	Result	Execution time	Memory
223553		tqbfjotld	Lampice (COCI19_lampice)	C++14	25 / 110	8 ms	1152 KiB

lampice

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

string findLongestPalindromicString(string text) {
    int N = text.size();
    if(N == 0)
        return "";
    N = 2*N + 1; //Position count
    int L[N]; //LPS Length Array
    L[0] = 0;
    L[1] = 1;
    int C = 1; //centerPosition
    int R = 2; //centerRightPosition
    int i = 0; //currentRightPosition
    int iMirror; //currentLeftPosition
    int expand = -1;
    int diff = -1;
    int maxLPSLength = 0;
    int maxLPSCenterPosition = 0;
    int start = -1;
    int en = -1;

    //Uncomment it to print LPS Length array
    //printf("%d %d ", L[0], L[1]);
    for (i = 2; i < N; i++){
        //get currentLeftPosition iMirror for currentRightPosition i
        iMirror  = 2*C-i;
        //Reset expand - means no expansion required
        expand = 0;
        diff = R - i;
        //If currentRightPosition i is within centerRightPosition R
        if(diff >= 0){
            if(L[iMirror] < diff) // Case 1
                L[i] = L[iMirror];
            else if(L[iMirror] == diff && R == N-1) // Case 2
                L[i] = L[iMirror];
            else if(L[iMirror] == diff && R < N-1){
                    L[i] = L[iMirror];
                    expand = 1;  // expansion required
            }
            else if(L[iMirror] > diff){
                L[i] = diff;
                expand = 1;  // expansion required
            }
        }
        else{
            L[i] = 0;
            expand = 1;  // expansion required
        }

        if (expand == 1){
            //Attempt to expand palindrome centered at currentRightPosition i
            //Here for odd positions, we compare characters and
            //if match then increment LPS Length by ONE
            //If even position, we just increment LPS by ONE without
            //any character comparison
            while (((i+L[i])<N&&(i-L[i])>0)&&(((i+L[i]+1)%2==0)||(text[(i+L[i]+1)/2]==text[(i-L[i]-1)/2]))){
                L[i]++;
            }
        }

        if(L[i] > maxLPSLength){
            maxLPSLength = L[i];
            maxLPSCenterPosition = i;
        }

        // If palindrome centered at currentRightPosition i
        // expand beyond centerRightPosition R,
        // adjust centerPosition C based on expanded palindrome.
        if (i + L[i] > R){
            C = i;
            R = i + L[i];
        }
        //Uncomment it to print LPS Length array
        //printf("%d ", L[i]);
    }
    //printf("\n");
    start = (maxLPSCenterPosition - maxLPSLength)/2;
    en = start + maxLPSLength - 1;
    //printf("start: %d end: %d\n", start, end);
    return text.substr(start,en-start+1);
}

int main(){
   int n;
   cin>>n;
   string str;
   cin>>str;
   printf("%d",findLongestPalindromicString(str).size());
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:89:56: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d",findLongestPalindromicString(str).size());
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^

• Subtask 1: 0 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37