Submission #997412

#	Time	Username	Problem	Language	Result	Execution time	Memory
997412		vjudge1	Palindromes (APIO14_palindrome)	C++17	23 / 100	1062 ms	24700 KiB

palindrome

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+5, base = 727, mod = 998244353;
unordered_map<int,int> cnt[N];
string s;
int pref[N << 1], pw[N << 1];

void update(int l, int r) // l and r are inclusive
{
  // [l + 1, ...., r - 1]
  int hsh = 0;
  // for(int i = l; i <= r; i++)
  // hsh = (1ll * hsh * base % mod + s[i]) % mod;
  
  hsh = 1ll * pref[l] * pw[r - l + 1] % mod - pref[r + 1];
  hsh = (hsh % mod + mod) % mod;
  
  cnt[(r - l + 1) / 2][hsh]++;
}

int main()
{
  cin >> s;
  int len = s.size();
  string t;

  t = "#";
  for(char i : s) {
    t += i; t += '#';
  }
  s = t;
  
  int n = s.size();
  pref[0] = 0;
  pw[0] = 1;
  for(int i = 0; i < n; i ++)
    {
      pw[i + 1] = 1ll * pw[i] * base % mod;
      pref[i + 1] = (1ll * pref[i] * base % mod + s[i]) % mod;
    }
  
  for(int c = 0; c < n; c++)
    {
      if(c != '#')
	update(c, c);
      int l = c - 1, r = c + 1;
      while(l >= 0 && r < s.size() && s[l] == s[r])
	{
	  if(s[l] == '#')
	    update(l, r);
	  l--, r++;
	}
    }

  
  long long ans = 0;
  for(int i = 1; i <= len; i ++)
    {
      int mx = 0;
      for(auto x : cnt[i])
	mx = max(mx, x.second);
      ans = max(ans, 1ll * mx * i);
    }
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |       while(l >= 0 && r < s.size() && s[l] == s[r])
      |                       ~~^~~~~~~~~~

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