Submission #47506

#	Time	Username	Problem	Language	Result	Execution time	Memory
47506		Waschbar	Palindromes (APIO14_palindrome)	C++17	23 / 100	1082 ms	4796 KiB

palindrome

///©Waschbar
#include <bits/stdc++.h>
#define tmm first
#define uu second.first
#define vv second.second
using namespace std;

const int MAXN = 1e5;
const int LOG = 20;
const int INF = 1e9;
const int MOD = 1e9+7;

int ans;
map < string,bool > used;
string s;

vector < int > pfunc(string str) {
        vector < int > p(str.size(),0);
            int j = 0;
        for(int i = 1; i < str.size(); i++) {
            while( j > 0 && str[j] != str[i])
                j = p[j-1];
            if(str[i] == str[j]) j++;
            p[i] = j;
        }

    return p;
}

void check(string t) {
    if(used[t]) return;
    used[t] = 1;
     vector < int > p;
     string tt = t + "#" + s;
     p = pfunc(tt);
     int cnt = 0;
     for(int i = 0; i < p.size(); i++)
        if(p[i] == t.size()) cnt++;
     //cout << t << " " << cnt << endl;
     ans = max(ans,(int)(t.size()*cnt));
}

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ans = 0;
    cin >> s;

    string t;
    for(int i = 0; i < s.size(); i++) {
        t = ""; t = s[i];
        int j = 1;
        while(i-j >= 0 && i+j < s.size() && s[i-j]==s[i+j]) {
             check(t);
             t = s[i-j] + t + s[i+j];
             j++;
        }
        check(t);
    }
    for(int i = 0; i < s.size()-1; i++) {
        t = ""; t = s[i]; t = t + s[i+1];
        if(s[i] != s[i+1]) continue;
        int j = 1;
        while(i-j >= 0 && i+j+1 < s.size() && s[i-j]==s[i+j+1]) {
             check(t);
             t = s[i-j] + t + s[i+j+1];
             j++;
        }
        check(t);
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'std::vector<int> pfunc(std::__cxx11::string)':
palindrome.cpp:20:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < str.size(); i++) {
                        ~~^~~~~~~~~~~~
palindrome.cpp: In function 'void check(std::__cxx11::string)':
palindrome.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < p.size(); i++)
                     ~~^~~~~~~~~~
palindrome.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(p[i] == t.size()) cnt++;
palindrome.cpp: In function 'int main()':
palindrome.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++) {
                    ~~^~~~~~~~~~
palindrome.cpp:55:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i-j >= 0 && i+j < s.size() && s[i-j]==s[i+j]) {
                           ~~~~^~~~~~~~~~
palindrome.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size()-1; i++) {
                    ~~^~~~~~~~~~~~
palindrome.cpp:66:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i-j >= 0 && i+j+1 < s.size() && s[i-j]==s[i+j+1]) {
                           ~~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27