Pagini recente » Cod sursa (job #194095) | Cod sursa (job #506887) | Cod sursa (job #2625550) | Cod sursa (job #2983676) | Cod sursa (job #2865846)
#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
const long long base = 26;
const long long MOD = 1000000000 + 7;
bool CheckPal(string s) {
int l = s.length();
for (int i = 0; i < l / 2; i++) {
if (s[i] != s[l - 1 - i]) {
return false;
}
}
return true;
}
void longestPal(string s) {
int size_of_str = s.size();
string LongestPal;
vector <int> front_hash(size_of_str + 1);
vector <int> back_hash(size_of_str + 1);
vector <long long> pow(size_of_str + 1);
pow[0] = 1;
front_hash[0] = s[0] - 'a';
back_hash[size_of_str - 1] = s[size_of_str - 1] - 'a';
for (int i = 0; i < size_of_str - 1; i++) {
front_hash[i + 1] = ((front_hash[i] * base) % MOD + s[i] - 'a') % MOD;
pow[i + 1] = ((pow[i] % MOD) * (base % MOD)) % MOD;
}
for (int i = size_of_str - 1; i >= 0; i--)
{
back_hash[i] = ((back_hash[i + 1] * base) % MOD + s[i] - 'a') % MOD;
}
/* for (auto& it : front_hash)
cout << it << " ";
cout << '\n';
for (auto& it : back_hash)
cout << it << " ";
cout << '\n';*/
int n_o_p = 0;
for (int i = size_of_str - 1 ; i >= 1; i--) {
for (int j = 0; j < i; j++)
{
string test;
test = s.substr(j, i - j);
int bh;
int fh;
bh = (back_hash[j] + MOD - (back_hash[i] * pow[i - j]) % MOD) % MOD;
fh = (front_hash[i] + MOD - (front_hash[j] * pow[i - j]) % MOD) % MOD;
if (bh == fh)
{
//cout << test << " and " << current_lenght << '\n';
if (CheckPal(test) == true && test !=" ") {
// cout << "it is palindrome: " << test << endl;
n_o_p++;
// cout << test << '\n';
}
}
}
}
cout << n_o_p + 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string str;
cin >> str;
longestPal(str);
return 0;
}