제출 #947640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947640		vjudge1	회문 (APIO14_palindrome)	C++17	0 / 100	9 ms	35420 KiB

palindrome

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

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}



const int N = 3e5+7, K = 26;
//====================================================================//


const int MAXN = 3e5+7; ///max length of string+3
namespace PalTree {
  struct node {
    int len; ///length of the pal of this node
    int sufflink; ///largest suff pal of this node
    int chain;///#of nodes on chain of suff links
    int next[26];///next[c] is the pal by adding c
  } tr[MAXN];
  int size;///# of nodes currently in Pal tr
  int suff;///max suff pal of curr prcessed prefix
  string s;///string we will built our Paltr on
  bool addLetter(int pos) {
    int cur = suff, curlen = 0, let = s[pos]-'a';
    while (true) {
      curlen = tr[cur].len;
      if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
        break; cur = tr[cur].sufflink;
    }
    if (tr[cur].next[let]) {
      suff = tr[cur].next[let]; return false;
    }
    suff = ++size; tr[cur].next[let] = size;
    tr[size].len = tr[cur].len+2;
    if (tr[size].len == 1) {
      tr[size].sufflink=2; tr[size].chain=1;
      return true;
    }
    while (true) {
      cur=tr[cur].sufflink;curlen=tr[cur].len;
     if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]){
        tr[size].sufflink = tr[cur].next[let];
        break;
      }
    }
    tr[size].chain=1+tr[tr[size].sufflink].chain;
    return true;
  }
  void initTree() {
    memset(tr,0,sizeof tr);///CAREFUL:TESTCASES
    size = 2; suff = 2;
    tr[1].len = -1; tr[1].sufflink = 1;
    tr[2].len = 0; tr[2].sufflink = 1;
  }
}

int cnt[N];
void testcase(){
	cin >> PalTree::s;
	PalTree::initTree();
	for(int i = 0; i < PalTree::s.size(); i++){
		PalTree::addLetter(i);
		cnt[PalTree::suff]++;
	}
	ll ans = 0;
	for(int i = PalTree::suff; i >= 2; i--){
		ans = max(ans, (ll)cnt[i] * PalTree::tr[i].len);
		cnt[PalTree::tr[i].sufflink] += cnt[i];
	}
	cout << ans << "\n";
	
}




int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(NULL);
	freopen("palindrome.in", "r", stdin);
	freopen("palindrome.out", "w", stdout);
	int T = 1;
	//cin >> T;
	
	for(int qq = 1; qq <= T; ++qq){
		//cout << "Case #" << qq << ": ";
		testcase();
	}
	return 0;
}

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

palindrome.cpp: In function 'bool PalTree::addLetter(int)':
palindrome.cpp:100:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  100 |       if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
      |       ^~
palindrome.cpp:101:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  101 |         break; cur = tr[cur].sufflink;
      |                ^~~
palindrome.cpp: In function 'void testcase()':
palindrome.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for(int i = 0; i < PalTree::s.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:153:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |  freopen("palindrome.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:154:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |  freopen("palindrome.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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