제출 #308047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
308047		Elephant52	Palindromes (APIO14_palindrome)	C++11	100 / 100	83 ms	66428 KiB

palindrome

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;

#define INF 1000000000
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)

void setIO(string name) {
    freopen((name+".in").c_str(), "r", stdin); 
    freopen((name+".out").c_str(), "w", stdout);
}

string s;

struct node {
    int next[26], suflink, len;
    ll num;
    node() {};
    vi adj;
} tree[300001];

//node tree[300001];
int num, suf;

bool add_letter(int pos) { //return 1 on new palindromes
    int cur = suf, letter = (s[pos]-'a'), curlen = 0;
    
    while(1) { //find longest palindromic suffix of s[0...pos-1] that can include s[pos]
        curlen = tree[cur].len;
        if (pos > curlen && s[pos-1-curlen] == s[pos]) break;
        cur = tree[cur].suflink;
    }
    
    if (tree[cur].next[letter]) { //if there exists a link from smaller palindrome to s[pos] + pal + s[pos] then do nothing
        suf = tree[cur].next[letter];
        tree[suf].num++;
        return 0;
    }
    
    //create a new palindrome with id num+1 in the tree
    
    suf = ++num;
    tree[num].num = 1;
    tree[num].len = tree[cur].len + 2; //add on s[pos]
    tree[cur].next[letter] = num;
    
    if (tree[num].len == 1) {
        tree[num].suflink = 2; //link to the empty palindrome
        tree[2].adj.PB(num);
        return 1;
    } 
    
    while(1) {
        cur = tree[cur].suflink;
        curlen = tree[cur].len;
        if (pos > curlen && s[pos-1-curlen] == s[pos]) {
            tree[num].suflink = tree[cur].next[letter];
            tree[tree[cur].next[letter]].adj.PB(num);
            break;
        }
    }
    
    return 1;
}

void dfs(int cur = 1) {
    for (auto edge : tree[cur].adj) {
        dfs(edge);
        tree[cur].num += tree[edge].num;
    }
}

void init() {
    num = suf = 2;
    tree[1].len = -1, tree[2].len = 0;
    tree[1].suflink = tree[2].suflink = 1;
    tree[1].adj.PB(2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> s;
    
    init();
    
    rep(i,0,s.length()) add_letter(i);
    
    ll ans = 0;
    
    dfs();
    
    rep(i,1,300001) ans = max(ans, (long long)tree[i].len * tree[i].num);
    
    cout << ans << endl;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:15:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,a,b) for (int i = a; i < b; i++)
......
   96 |     rep(i,0,s.length()) add_letter(i);
      |         ~~~~~~~~~~~~~~                
palindrome.cpp:96:5: note: in expansion of macro 'rep'
   96 |     rep(i,0,s.length()) add_letter(i);
      |     ^~~
palindrome.cpp: In function 'void setIO(std::string)':
palindrome.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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