Advertisement
kirill1567

Untitled

Jan 21st, 2017
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <vector>
  3. #include <cmath>
  4. #include <math.h>
  5. #include <map>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <utility>
  9. #include <queue>
  10. #include <fstream>
  11. #define fo(a,b,c) for(int a=b;a<c;a++);
  12. #define module 1073676287
  13. /*hello world lol
  14.  *
  15.  */
  16. int64_t get_hash(int l,int r,std::vector<int64_t>hash,std::vector<int64_t>stepeni_P){
  17.     int64_t result_hash=(hash[r]-hash[l-1])/stepeni_P[l];
  18.     return result_hash;
  19. }
  20. int main(int argc, char** argv) {
  21.     int n,P;
  22.     std::cin>>n;//длина строки
  23.     std::cin>>P; //мощность алфавита если так можно выразиться
  24.     std::vector<int>in(n);//входной вектор
  25.     for(int i=0;i<n;i++){
  26.         std::cin>>in[i];
  27.     }
  28.     std::vector<int64_t>hash(in.size(),0);//хеши
  29.     std::vector<int64_t>stepeni_P(in.size(),0);//значения степеней основания по модулю
  30.     int stepen=0;
  31.     hash[0]=in[0];//задаем первые значения
  32.     stepeni_P[0]=1;
  33.     for(int i=1;i<hash.size();i++){
  34.         stepeni_P[i]=(stepeni_P[i-1]*P);
  35.         hash[i]=((in[i])*stepeni_P[i]+hash[i-1]);
  36.     }
  37.     std::cout<<in.size()<<"\n";
  38.     int result_length=in.size();
  39.     for(int i=1;i<in.size();i++){
  40.         result_length--;
  41.         int l=in.size()-result_length;
  42.         int r=l+l-1;
  43.         if(hash[l-1]==get_hash(l,r,hash,stepeni_P)){
  44.             std::cout<<result_length<<std::endl;
  45.         }
  46.     }
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement