fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <string>
  7. using namespace std;
  8. char a[1000002],b[1000002];
  9. int main() {
  10.     int n;
  11.     scanf("%d",&n);
  12.     for(int i=0;i<n;++i){
  13.         int s;
  14.         scanf("%d",&s);
  15.         scanf("%s",a);
  16.         scanf("%s",b);
  17.         int m=s;
  18.         int n=strlen(b);
  19.         unsigned int p=41;
  20.         unsigned int q=1000000007,h=1;
  21.         unsigned int hasz1=0,hasz2=0;
  22.         for(int i=0;i<m;++i){
  23.             hasz1=((hasz1*p)+a[i]);
  24.         }
  25.         for(int i=0;i<m;++i){
  26.             hasz2=((hasz2*p)+b[i]);
  27.             if(i>0)h=(h*p);;
  28.         }
  29.         for(int i=0;i<=n-m;++i){
  30.             if(hasz1==hasz2){
  31.                 int j=0;
  32.                 bool fla=0;
  33.                 /*
  34.                 while(j<m){
  35.                     if(a[j]!=b[i+j]){ // O to
  36.                         fla=1;
  37.                         break;
  38.                     }
  39.                     ++j;
  40.                 }
  41.                 if(fla==0)
  42.                  */
  43.                     printf("%d\n",i);
  44.             }
  45.             if(i<n-m){
  46.                 hasz2=(p*(hasz2-b[i]*h));
  47.                 hasz2=(hasz2+b[i+m]);
  48.             }
  49.         }
  50.     }
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 17192KB
comments (?)
stdin
copy 
1
0

aaaaaa
stdout
copy 
0
https://ideone.com/39GJQs
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!