// Greedy solution with rolling string hashes. Repeatedly takes the smallest possible
// chunk from the sides, using string hashes to quickly check for equality of chunks.
// Hash updating and comparison takes O(1), so the total running time is O(n).
#include <bits/stdc++.h>
#define MAX_WORD_LENGTH 5100000
int longest_palindromic_partition(char *word) {
const int n = strlen(word);
const unsigned int base = 131;
int done_chars = 0;
int n_chunks = 0;
while (done_chars * 2 < n) {
unsigned int left_hash=0, right_hash=0;
unsigned int base_power=1;
for (int chunk_size=1; true; chunk_size++) {
const int l = done_chars;
const int r = n - done_chars - chunk_size;
if (l + chunk_size - 1 >= r) {
return n_chunks + 1;
}
base_power = chunk_size == 1 ? 1 : base_power * base;
left_hash += static_cast<unsigned int>(word[l + chunk_size - 1]) * base_power;
right_hash = static_cast<unsigned int>(word[r]) + right_hash * base;
if (left_hash == right_hash && strncmp(word + l, word + r, chunk_size) == 0) {
n_chunks += 2;
done_chars += chunk_size;
break;
}
}
}
return n_chunks;
}
int main() {
int n;
char word[MAX_WORD_LENGTH];
scanf("%d\n", &n);
for (int i=0; i<n; i++) {
scanf("%s\n", word);
assert(strlen(word) <= MAX_WORD_LENGTH);
printf("%d\n", longest_palindromic_partition(word));
}
return 0;
}
Compilation message
palindromic.c:5:10: fatal error: bits/stdc++.h: No such file or directory
5 | #include <bits/stdc++.h>
| ^~~~~~~~~~~~~~~
compilation terminated.
