제출 #32153

#제출 시각아이디문제언어결과실행 시간메모리
32153minimario회문 (APIO14_palindrome)C++14
0 / 100
29 ms53184 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 300005; struct node { int len; int next[26]; int suff; int ct; }; node t[MAX]; int i = 0; int ans = 0; void roots() { t[0].len = -1; t[0].suff = 0; t[1].len = 0; t[1].suff = 0; } int ct = 2; int maxsuff = 1; string s; void add(int pos) { int j = maxsuff; int c = s[pos] - 'a'; // the character while (s[pos-t[j].len-1] != s[pos]) { j = t[j].suff; } if (t[j].next[c] == 0) { t[j].next[c] = ct; t[ct].len = t[j].len + 2; ct++; } maxsuff = t[j].next[c]; if (j == 0) { t[maxsuff].suff = 1; } else { j = t[j].suff; while (s[pos-t[j].len-1] != s[pos]) { j = t[j].suff; } if (t[j].next[c] == 0) { t[j].next[c] = ct; t[ct].len = t[j].len + 2; ct++; } t[maxsuff].suff = t[j].next[c]; } t[maxsuff].ct++; } bool v[MAX]; vector<int> g[MAX]; void create() { for (int i=2; i<=MAX; i++) { if (t[i].suff > 1) { g[t[i].suff].push_back(i); } } } void dfs(int u) { v[u] = true; for (int i : g[u]) { dfs(i); t[u].ct += t[i].ct; } } int main() { //freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> s; s = " " + s; roots(); for (int i=1; i<s.length(); i++) { add(i); } v[0] = v[1] = true; create(); for (int i=2; i<=MAX; i++) { if (!v[i]) { dfs(i); } } long long maxi = 0; for (int i=2; i<MAX; i++) { maxi = max(maxi, (long long)t[i].len * (long long)t[i].ct); } cout << maxi << endl; }

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

palindrome.cpp: In function 'int main()':
palindrome.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<s.length(); i++) {
                 ^
palindrome.cpp:87:11: warning: iteration 300003u invokes undefined behavior [-Waggressive-loop-optimizations]
   if (!v[i]) { dfs(i); }
           ^
palindrome.cpp:86:17: note: containing loop
  for (int i=2; i<=MAX; i++) {
                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...