Longest Palindrome (CSES problem set)

Problem set

(TLE answer) O(n²) approach

const ll Z_Mul = 26;ll hash_sum[1000000 + 2];ll hash_sum_rev[1000000 + 2], n;bool ispalindrome(ll l, ll r){ll val1 = hash_sum[r];if (l > 0)val1 -= hash_sum[l - 1];if (val1 < 0)val1 += MOD;val1 = (val1 * power(power(26, l), MOD - 2)) % MOD;ll temp = r;r = n - 1 - l;l = n - 1 - temp;ll val2 = hash_sum_rev[r];if (l > 0)val2 -= hash_sum_rev[l - 1];if (val2 < 0)val2 += MOD;val2 = (val2 * power(power(26, l), MOD - 2)) % MOD;return val1 == val2;}void solve(){string a;cin >> a;n = a.size();hash_sum[0] = power(26, 1) * a[0];for (ll i = 1; i < n; i++){hash_sum[i] = (hash_sum[i - 1] + (power(26, i + 1) * a[i]) % MOD) % MOD;}string rev_a = "";for (auto i : a)rev_a = i + rev_a;hash_sum_rev[0] = power(26, 1) * rev_a[0];for (ll i = 1; i < n; i++){hash_sum_rev[i] = (hash_sum_rev[i - 1] + (power(26, i + 1) * rev_a[i]) % MOD) % MOD;}for (ll len = n; len >= 1; len--){for (ll i = 0; i + len - 1 < n; i++){if (ispalindrome(i, len + i - 1)){for (ll j = i; j - i < len; j++){cout << a[j];}return;}}}}

Manachar’s algorithm O(n)

void solve(){string a;cin >> a;string s = "";s += '@';s += '#';for (auto i : a)s += i, s += '#';s += '$';a = s;n = a.size();ll mini[n] = {0};ll c = 0, r = 0, maxi = 0;for (ll i = 1; i < n; i++){ll mir = 2 * c - i;if (r > i){mini[i] = min(r - i, mini[mir]);}while (s[i - mini[i] - 1] == s[i + mini[i] + 1]){mini[i]++;}if (mini[i] + i > r){r = mini[i] + i;c = i;}maxi = max(maxi, mini[i]);}REP(i, 0, n){if (mini[i] == maxi){string ans = "";for (ll j = i - mini[i]; j <= i + mini[i]; j++){if (s[j] != '#' && s[j] != '$' && s[j] != '@')ans += s[j];}cout << ans;return;}}}

software developer