Untitled

 avatar
unknown
c_cpp
a year ago
1.0 kB
7
Indexable
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

const int N = 1e6 + 10;
const long long X = 37, M = 1e9 + 7;

long long pw[N];
long long Hash[N], arr[N / 2];

int main()
{
    string s;
    cin >> s;

    pw[0] = 1;
    for ( int i = 1; i < N; i++ )
        pw[i] = pw[i - 1] * X % M;

    Hash[0] = ( Hash[0] + s[0] * pw[0] % M ) % M;

    for ( int j = 1; j < s.length(); j++ )
    {
        Hash[j] = ( Hash[j - 1] + s[j] * pw[j] % M ) % M;
    }

    int j = 0;

    for ( int i = 0; i < s.length(); i++ )
    {
        long long a = Hash[s.length() - i - 2];
        int x = i + 1;
        while ( x )
        {
            a = a * X % M;
            x--;
        }
        if ( Hash[i] == ( Hash[s.length() - 1] - a ))         
        {
            arr[j] = i + 1; 
            j++;
        }
    }

    for ( int i = 0; i < j; i++ )
    {
        cout << arr[i];
        if ( i != j - 1 ) cout << " ";
    }
    cout << "\n";

}
Editor is loading...
Leave a Comment