/** I can do this all day **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
char S[N];
string s;
int rnk[LOG][N], A[N], T, n;
bool cmp(int i, int j)
{
if(rnk[T - 1][i] == rnk[T - 1][j])
{
if(max(i, j) + (1 << (T - 1)) > n) return i > j;
return rnk[T - 1][i + (1 << (T - 1))] < rnk[T - 1][j + (1 << (T - 1))];
}
return rnk[T - 1][i] < rnk[T - 1][j];
}
void B()
{
for(int i = 1; i <= n; i ++)
{
A[i] = i;
rnk[0][i] = s[i] - 'a' + 1;
}
for(T = 1; T < LOG; T ++)
{
sort(A + 1, A + n + 1, cmp);
rnk[T][A[1]] = 1;
for(int i = 2; i <= n; i ++)
{
rnk[T][A[i]] = rnk[T][A[i - 1]] + cmp(A[i - 1], A[i]);
}
}
}
int lcp(int i, int j)
{
int tot = 0;
for(T = LOG - 1; ~T; T --)
{
if(max(i, j) + (1 << T) - 1 > n || rnk[T][i] != rnk[T][j]) continue;
tot |= 1 << T;
i += 1 << T;
j += 1 << T;
}
return tot;
}
int is_eq(int i, int j, int sz)
{
if(lcp(i, j - sz + 1) >= sz) return 1;
return 0;
}
inline void solve()
{
memset(rnk, 0, sizeof rnk);
scanf("%s", &S);
s = S;
n = (int)s.size();
s = "." + s;
B();
int l = 1, r = n, ans = 1, sz = 1;
while(l <= r)
{
while(!is_eq(l, r, sz)) sz ++;
if(l + sz - 1 >= r - sz + 1) break;
if(l + sz == r - sz + 1) { ans ++; break; }
ans += 2;
l += sz;
r -= sz;
}
printf("%d\n", ans);
}
int main()
{
int q;
scanf("%d", &q);
while(q--)
{
solve();
}
return 0;
}
/*!
stay away from negative people they have a problem for every solution !
*/
Compilation message
palindromic.cpp: In function 'void solve()':
palindromic.cpp:83:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000010]' [-Wformat=]
83 | scanf("%s", &S);
| ~^
| |
| char*
palindromic.cpp: In function 'int main()':
palindromic.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
104 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
palindromic.cpp: In function 'void solve()':
palindromic.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%s", &S);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
