제출 #706062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706062		mahdi_hasnat	회문 (APIO14_palindrome)	C++17	100 / 100	31 ms	41564 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
typedef pair<int,int> pii;
#define ALL(x) x.begin(),x.end()

const int N = 3e5 +5;
const int oo = 1e9+7;


struct PalindromicTree {
 struct node {
  int nxt[26], len, st, en, link, diff, slink, cnt, oc;
 };
 string s;vector<node> t;
 int sz, last;
 PalindromicTree() {}
 PalindromicTree(string _s) {
  s = _s;
  int n = s.size();
  t.clear();
  t.resize(n + 9);sz = 2, last = 2;
  t[1].len = -1, t[1].link = 1;
  t[2].len = 0, t[2].link = 1;
  t[1].diff = t[2].diff = 0;
  t[1].slink = 1;t[2].slink = 2;
 }
 int extend(int pos) { // returns 1 if it creates a new palindrome
  int cur = last, curlen = 0;
  int ch = s[pos] - 'a';
  while (1) {curlen = t[cur].len;
   if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
   cur = t[cur].link;
  }
  if (t[cur].nxt[ch]) {last = t[cur].nxt[ch];
   t[last].oc++;
   return 0;
  }
  sz++;last = sz;
  t[sz].oc = 1;t[sz].len = t[cur].len + 2;
  t[cur].nxt[ch] = sz;t[sz].en = pos;
  t[sz].st = pos - t[sz].len + 1;
  if (t[sz].len == 1) {
   t[sz].link = 2;t[sz].cnt = 1;
   t[sz].diff = 1;t[sz].slink = 2;
   return 1;
  }
  while (1) {
   cur = t[cur].link;curlen = t[cur].len;
   if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
    t[sz].link = t[cur].nxt[ch];
    break;
   }
  }
  t[sz].cnt = 1 + t[t[sz].link].cnt;
  t[sz].diff = t[sz].len - t[t[sz].link].len;
  if (t[sz].diff == t[t[sz].link].diff) t[sz].slink = t[t[sz].link].slink;
  else t[sz].slink = t[sz].link;
  return 1;
 }
 void calc_occurrences() {
  for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc;
 }
 vector<array<int, 2>> minimum_partition() { //(even, odd), 1 indexed
  int n = s.size();
  vector<array<int, 2>> ans(n + 1, {0, 0}), series_ans(n + 5, {0, 0});
  ans[0][1] = series_ans[2][1] = 1e9;
  for (int i = 1; i <= n; i++) {
   extend(i - 1);
   for (int k = 0; k < 2; k++) {
    ans[i][k] = 1e9;
    for (int v = last; t[v].len > 0; v = t[v].slink) {
     series_ans[v][!k] = ans[i - (t[t[v].slink].len + t[v].diff)][!k];
     if (t[v].diff == t[t[v].link].diff) series_ans[v][!k] = min(series_ans[v][!k], series_ans[t[v].link][!k]);
     ans[i][k] = min(ans[i][k], series_ans[v][!k] + 1);
    }
   }
  }
  return ans;
 }
} t;

// int32_t main() {
//  string s;cin >> s;
//  PalindromicTree t(s);
//  for (int i = 0; i < s.size(); i++) t.extend(i);
//  t.calc_occurrences();
//  long long ans = 0;
//  for (int i = 3; i <= t.sz; i++) ans += t.t[i].oc;
//  cout << ans << '\n';
//  //auto ans = t.minimum_partition();
//  // for (int i = 1; i <= s.size(); i++) {
//  //   cout << (ans[i][1] == 1e9 ? -1 : ans[i][1]) << ' ';
//  //   cout << (ans[i][0] == 1e9 ? -2 : ans[i][0]) << '\n';
//  // }
// }


void solve()
{
	string s;
	cin>>s;
	PalindromicTree t(s);
	for(int i=0;i<s.size();i++)
	{
		t.extend(i);
	}
	t.calc_occurrences();
	ll ans = 0;
	for(int i=3;i<=t.sz;i++)
	{
		ans=max(ans, t.t[i].oc *1LL* t.t[i].len);
	}
	cout<<ans<<'\n';
}
/*

*/

int32_t main()
{
#ifndef APURBA
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T=1;
    // cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

		   	  	 			 	  			    		  	 	

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

palindrome.cpp: In function 'void solve()':
palindrome.cpp:111:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i=0;i<s.size();i++)
      |              ~^~~~~~~~~

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