Cod sursa(job #2865846)

Utilizator Ii7MoOdYxG4meSbaroi Ionut-Alexandru Ii7MoOdYxG4me Data 9 martie 2022 11:09:25
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#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;
}