#include <bits/stdc++.h>
using namespace std;
long long prefiks[100005], sufiks[100005], potegi[100005], wynik;
int poprawka, dodawanie[100005][30], maks;
string slowo;
bool sprawdzenie_nieparzyste(int x, int i, int zmiana, int miejsce){
//cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 << " " << potegi[(x * 2 + 1)] << " " << sufiks[slowo.size() - i + x] << " " << sufiks[slowo.size() - i - x - 1] << " " << i << " " << x << "\n";
//cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] << " " << prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] << " " << x << "\n";
if (poprawka == -1){
if (sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 == prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] % 1000000009)
return true;
}
else{
if (miejsce == 1){
if (sufiks[slowo.size() - i + x] - (potegi[x - zmiana] * slowo[i - zmiana]) + (potegi[x - zmiana] * slowo[i + zmiana]) - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 == prefiks[i + x + 1] - (potegi[x + zmiana] * slowo[i - zmiana]) + (potegi[x + zmiana] * slowo[i + zmiana]) - prefiks[i - x] * potegi[(x * 2 + 1)] % 1000000009)
return true;
}
if (miejsce == 2){
if (sufiks[slowo.size() - i + x] + (potegi[x + zmiana] * slowo[i - zmiana]) - (potegi[x + zmiana] * slowo[i + zmiana]) - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 == prefiks[i + x + 1] + (potegi[x - zmiana] * slowo[i - zmiana]) - (potegi[x - zmiana] * slowo[i + zmiana]) - prefiks[i - x] * potegi[(x * 2 + 1)] % 1000000009)
return true;
}
}
return false;
}
bool sprawdzenie_parzyste(int x, int i, int zmiana, int miejsce){
//cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 << " " << potegi[(x * 2 + 1)] << " " << sufiks[slowo.size() - i + x] << " " << sufiks[slowo.size() - i - x - 1] << " " << i << " " << x << "\n";
//cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] << " " << prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] << " " << x << "\n";
if (poprawka == -1){
if (sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 2] * potegi[(x * 2 + 2)] % 1000000009 == prefiks[i + x + 2] - prefiks[i - x] * potegi[(x * 2 + 2)] % 1000000009)
return true;
}
else{
if (miejsce == 1){
//cout << i - zmiana << " " << i + zmiana + 1 << " " << i << " $\n";
if (sufiks[slowo.size() - i + x] - (potegi[x - zmiana] * slowo[i - zmiana]) + (potegi[x - zmiana] * slowo[i + zmiana + 1]) - sufiks[slowo.size() - i - x - 2] * potegi[(x * 2 + 2)] % 1000000009 == prefiks[i + x + 2] - (potegi[x + zmiana + 1] * slowo[i - zmiana]) + (potegi[x + zmiana + 1] * slowo[i + zmiana + 1]) - prefiks[i - x] * potegi[(x * 2 + 2)] % 1000000009)
return true;
}
if (miejsce == 2){
//cout << i - zmiana << " " << i + zmiana + 1 << " " << i << " #\n";
if (sufiks[slowo.size() - i + x] + (potegi[x + zmiana + 1] * slowo[i - zmiana]) - (potegi[x + zmiana + 1] * slowo[i + zmiana + 1]) - sufiks[slowo.size() - i - x - 2] * potegi[(x * 2 + 2)] % 1000000009 == prefiks[i + x + 2] + (potegi[x - zmiana] * slowo[i - zmiana]) - (potegi[x - zmiana] * slowo[i + zmiana + 1]) - prefiks[i - x] * potegi[(x * 2 + 2)] % 1000000009)
return true;
}
}
return false;
}
int bin_search_nieparzysty(int i, int zmiana, int miejsce){
int pomocnicza = slowo.length() - 1 - i;
int poczatek = zmiana, koniec = min(i, pomocnicza), srodek, wynik_bin = -1;
if (poczatek > koniec)
return 0;
while(poczatek <= koniec){
srodek = (poczatek + koniec) / 2;
//if (zmiana)
//cout << srodek << " " << i << " |\n";
if (sprawdzenie_nieparzyste(srodek, i, zmiana, miejsce)){
//cout << zmiana << " " << srodek << "\n";
poczatek = srodek + 1;
wynik_bin = srodek;
}
else
koniec = srodek - 1;
}
//cout << wynik_bin + 1 << " ";
return wynik_bin + 1 - zmiana;
}
int bin_search_parzysty(int i, int zmiana, int miejsce){
int pomocnicza = slowo.length() - 2 - i;
int poczatek = zmiana, koniec = min(i, pomocnicza), srodek, wynik_bin = -1;
if (poczatek > koniec)
return 0;
while(poczatek <= koniec){
srodek = (poczatek + koniec) / 2;
//cout << srodek << "\n";
if (sprawdzenie_parzyste(srodek, i, zmiana, miejsce)){
//cout << 1 << "\n";
poczatek = srodek + 1;
wynik_bin = srodek;
}
else
koniec = srodek - 1;
}
//cout << wynik_bin + 1 << " ";
return wynik_bin + 1 - zmiana;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> slowo;
potegi[0] = 1;
int dlugosc = slowo.size();
for (int i = 1; i <= dlugosc; i++){
potegi[i] = 37 * potegi[i - 1];
potegi[i] %= 1000000009;
}
for (int i = 1; i <= dlugosc; i++){
prefiks[i] = prefiks[i - 1] * 37 + slowo[i - 1];
sufiks[i] = sufiks[i - 1] * 37 + slowo[dlugosc - i];
//cout << sufiks[i] << " " << sufiks[i] % 1000000009 << "\n";
prefiks[i] %= 1000000009;
sufiks[i] %= 1000000009;
}
for (int i = 0; i < dlugosc; i++){
poprawka = -1;
poprawka = bin_search_nieparzysty(i, 0, 0);
wynik += poprawka;
if (i - poprawka >= 0 && i + poprawka < dlugosc){
dodawanie[i - poprawka][int(slowo[i + poprawka] - 'a')] += bin_search_nieparzysty(i, poprawka, 1);
dodawanie[i + poprawka][int(slowo[i - poprawka] - 'a')] += bin_search_nieparzysty(i, poprawka, 2);
maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka] - 'a'], dodawanie[i + poprawka][slowo[i - poprawka] - 'a']));
//cout << dodawanie[i - poprawka][slowo[i + poprawka]] << " " << dodawanie[i + poprawka][slowo[i - poprawka]] << " " << i << " 1\n";
}
//cout << poprawka << " 1\n";
if (i < dlugosc - 1){
poprawka = -1;
poprawka = bin_search_parzysty(i, 0, 0);
//cout << poprawka << " 2\n";
wynik += poprawka;
if (i - poprawka >= 0 && i + poprawka + 1 < dlugosc){
dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'] += bin_search_parzysty(i, poprawka, 1);
dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] += bin_search_parzysty(i, poprawka, 2);
maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'], dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a']));
//cout << dodawanie[i - poprawka][slowo[i + poprawka + 1]] << " " << dodawanie[i + poprawka + 1][slowo[i - poprawka]] << " " << i << " 2\n";
}
}
maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'], dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a']));
}
wynik += maks;
cout << wynik;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
