Untitled
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