#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define TASKNAME "ppar"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MASK(i) (1LL << i)
#define ii pair<int, int>
#define BIT(x, i) (((x) >> (i))&1)
#define pb push_back
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
using namespace std;
string str;
int n;
template<typename T> bool maximize(T &a, T b){ if (a < b) {a = b; return true; } return false; }
template<typename T> bool minimize(T &a, T b){ if (a > b) {a = b; return true; } return false; }
const int MAXN = 1e6 + 9;
namespace subtask1{
bool check(){
return n <= 300;
}
int dp[303][303];
int lps[303][303];
/**
sub này ta có thể qhđ để giải.
**/
void solve(){
FORD(i, n, 1){
FORD(j, n, 1){
dp[i][j] = 0;
lps[i][j] = 0;
if (str[i] == str[j]) lps[i][j] = 1 + lps[i + 1][j + 1];
}
}
FOR(len, 1, n){
FOR(i, 1, n - len + 1){
int j = i + len - 1;
dp[i][j] = 1;
FOR(k, i, j - 1){
int len1 = k - i + 1;
int len2 = len1;
int t = j - len2 + 1;
if (lps[i][t] >= len1 and k < t) maximize(dp[i][j], dp[k + 1][t - 1] + 2);
}
}
}
printf("%lld\n", dp[1][n]);
}
}
namespace subtask2{
bool check(){
return n <= 10000;
}
vector<int> position[27];
int KMP[MAXN];
char temp[MAXN];
int build(int l, int r){
KMP[1] = 0;
FOR(i, l, r){
KMP[i - l + 1] = 0;
temp[i - l + 1] = str[i];
// printf("%c", temp[i - l + 1]);
}
int len = r - l + 1;
// printf("\n");
FOR(i, 2 , len){
int j = KMP[i - 1];
while(j > 0 and temp[j + 1] != temp[i]){
j = KMP[j];
}
if (temp[j + 1] == temp[i]) KMP[i] = j + 1;
// printf("%lld ", KMP[i]);
}
// printf("\n");
int mn = KMP[len];
if (mn == 0) return len;
while(mn > 0){
if (KMP[mn] == 0) return mn;
mn = KMP[mn];
}
}
void solve(){
int l = 1, r = n;
int ans = 0;
while(l <= r){
int len = build(l, r);
// printf("%lld %lld %lld %lld\n", len, ans, l, r);
if (len == r - l + 1){
ans++;
}
else ans+=2;
l = l + len;
r = r - len;
}
printf("%lld\n", ans);
}
}
namespace subtask3{
bool check(){
return true;
}
const ii P = ii(113, 97);
const ii MOD = ii(1e9 + 7, 998244353);
int cong(int a, int b, int mod){
return (a + b) % mod;
}
int tru(int a, int b, int mod){
return ((a - b) % mod + mod) % mod;
}
int nhan(int a, int b, int mod){
return (1LL * a * b) % mod;
}
ii operator + (ii a, ii b){
return ii(cong(a.fi, b.fi, MOD.fi), cong(a.se, b.se, MOD.se));
}
ii operator - (ii a, ii b){
return ii(tru(a.fi, b.fi, MOD.fi), tru(a.se, b.se, MOD.se));
}
ii operator * (ii a, ii b){
return ii(nhan(a.fi, b.fi, MOD.fi), nhan(a.se, b.se, MOD.se));
}
ii hashCode[MAXN], PW[MAXN];
ii getHash(int l, int r){
return hashCode[r] - hashCode[l - 1] * PW[r - l + 1];
}
bool operator == (ii a, ii b){
return (a.fi == b.fi and a.se == b.se);
}
vector<int> position[27];
void solve(){
PW[0] = {1, 1};
FOR(i, 1, n){
PW[i] = PW[i - 1] * P;
}
FOR(i, 1, n){
hashCode[i] = hashCode[i - 1] * P + ii(str[i] - 'a' + 1, str[i] - 'a' + 1);
position[str[i] - 'a'].pb(i);
}
// ii g1 = getHash(1, 2);
// ii g2 = getHash(5, 6);
// printf("%lld %lld\n", g1.fi, g1.se);
// printf("%lld %lld\n", g2.fi, g2.se);
int l = 1, r = n, ans = 0;
while(l <= r){
int mn = r - l + 1;
// printf("??");
FORD(i, (int) position[(str[l] - 'a')].size() - 1, 0){
int v = position[(str[l] - 'a')][i];
// printf("%lld %lld\n", l, v);
if (v < l) {
mn = r - l + 1; break;
}
ii g1 = getHash(l, l + r - v);
ii g2 = getHash(v, r);
// printf("%lld %lld\n", g1.fi, g1.se);
// printf("%lld %lld\n", g2.fi, g2.se);
if (getHash(l, l + r - v) == getHash(v, r)) {
minimize(mn, r - v + 1);
// printf("%lld %lld\n", l, v);
break;
}
}
if (mn == r - l + 1) ans++;
else ans += 2;
l = l + mn;
r = r - mn;
FOR(i, 0, 25){
while(position[i].size() > 0 and position[i].back() > r) position[i].pop_back();
}
}
printf("%lld\n", ans);
}
}
main(){
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
int t;
cin >> t;
while(t--){
cin >> str;
n = str.length();
str = '#' + str;
// if (subtask1::check()) subtask1::solve();
// if (subtask2::check()) subtask2::solve();
if (subtask3::check()) subtask3::solve();
}
}
Compilation message
palindromic.cpp: In function 'void subtask3::solve()':
palindromic.cpp:175:20: warning: variable 'g1' set but not used [-Wunused-but-set-variable]
175 | ii g1 = getHash(l, l + r - v);
| ^~
palindromic.cpp:176:20: warning: variable 'g2' set but not used [-Wunused-but-set-variable]
176 | ii g2 = getHash(v, r);
| ^~
palindromic.cpp: At global scope:
palindromic.cpp:199:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
199 | main(){
| ^~~~
palindromic.cpp: In function 'long long int subtask2::build(long long int, long long int)':
palindromic.cpp:91:5: warning: control reaches end of non-void function [-Wreturn-type]
91 | }
| ^
palindromic.cpp: In function 'int main()':
palindromic.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
202 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
472 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
472 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1496 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1020 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1496 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
472 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1496 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1020 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1496 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1324 KB |
Output is correct |
| 14 |
Correct |
356 ms |
92400 KB |
Output is correct |
| 15 |
Correct |
171 ms |
64740 KB |
Output is correct |
| 16 |
Correct |
276 ms |
92276 KB |
Output is correct |
| 17 |
Correct |
185 ms |
47244 KB |
Output is correct |
