Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <vector>
- #include <cmath>
- #include <math.h>
- #include <map>
- #include <algorithm>
- #include <iostream>
- #include <utility>
- #include <queue>
- #include <fstream>
- #define fo(a,b,c) for(int a=b;a<c;a++);
- #define module 1073676287
- /*hello world lol
- *
- */
- int64_t get_hash(int l,int r,std::vector<int64_t>hash,std::vector<int64_t>stepeni_P){
- int64_t result_hash=(hash[r]-hash[l-1])/stepeni_P[l];
- return result_hash;
- }
- int main(int argc, char** argv) {
- int n,P;
- std::cin>>n;//длина строки
- std::cin>>P; //мощность алфавита если так можно выразиться
- std::vector<int>in(n);//входной вектор
- for(int i=0;i<n;i++){
- std::cin>>in[i];
- }
- std::vector<int64_t>hash(in.size(),0);//хеши
- std::vector<int64_t>stepeni_P(in.size(),0);//значения степеней основания по модулю
- int stepen=0;
- hash[0]=in[0];//задаем первые значения
- stepeni_P[0]=1;
- for(int i=1;i<hash.size();i++){
- stepeni_P[i]=(stepeni_P[i-1]*P);
- hash[i]=((in[i])*stepeni_P[i]+hash[i-1]);
- }
- std::cout<<in.size()<<"\n";
- int result_length=in.size();
- for(int i=1;i<in.size();i++){
- result_length--;
- int l=in.size()-result_length;
- int r=l+l-1;
- if(hash[l-1]==get_hash(l,r,hash,stepeni_P)){
- std::cout<<result_length<<std::endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement