fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. typedef long long int ll;
  4. #define mod 1000000007
  5. ll gcd (ll a, ll b) {return ( a ? gcd(b%a, a) : b );}
  6. ll modPow(ll a,ll b,ll MOD){ll x=1,y=a;while(b>0){if(b%2 == 1){x=(x*y)%MOD;}b/=2;y = (y*y)%MOD;}return x;}
  7. ll modInverse(ll a,ll p){return modPow(a,p-2,p);}
  8.  
  9.  
  10.   char pat[10000000];
  11. char text[10000000];
  12. const int b=127;
  13.  
  14. bool check(int i,int m)
  15. {
  16.     for(int j=i;j<i+m;j++)
  17.     if(text[j]!=pat[j-i])
  18.     return false;
  19.     return true;
  20. }
  21. ll calc(char * s,int len)
  22. {
  23.     ll res=0;
  24.     for(int i=0;i<len;i++)
  25.     res=(((res)%mod*(b%mod))%mod+s[i]%mod)%mod;
  26.  
  27.     return res;
  28. }
  29.  
  30. ll recalc(string s,ll len,ll i,ll prev,ll H)
  31. {
  32.  
  33.     prev=(((( (prev%mod-((s[i-len]%mod)*(H%mod))%mod+mod) %mod) %mod)*(b%mod) )%mod+s[i]%mod)%mod;
  34.     return prev;
  35. }
  36.  
  37. void found()
  38. {
  39.    int n=strlen(text), m=strlen(pat);
  40.     ll hp=calc(pat,m);
  41.     if(m>n)
  42.     {
  43.       printf("\n");return;
  44.     }
  45.  
  46.  
  47.     ll ht=calc(text,m);
  48.     ll H=1;
  49.      for (int i = 0; i < m-1; i++)
  50.         H = ((H%mod)*(b%mod))%mod;
  51.  
  52.     if(ht==hp)
  53.     {
  54.         if(check(0,m))
  55.        printf("0\n");
  56.     }
  57.  
  58.     // printf("%d %d\n",ht,hp);
  59.  
  60.     for(int i=m;i<n;i++)
  61.     {
  62.         ht=recalc(text,m,i,ht,H);
  63.          //printf("%d %d\n",ht,hp);
  64.         if(ht==hp)
  65.          if(check(i-m+1,m))
  66.          printf("%d\n",i-m+1);
  67.     }
  68.     printf("\n");
  69. }
  70.  
  71. int main()
  72. {
  73.         int n;
  74.    while(scanf("%d\n",&n)!=EOF)
  75.    {
  76.     memset(pat,0,sizeof(pat));
  77.  
  78.     memset(text,0,sizeof(text));
  79.  
  80.     scanf("%s",pat);
  81.       scanf("%s",text);
  82.  
  83.     found();
  84.     }
  85. }
Success #stdin #stdout 0.01s 34760KB
comments (?)
stdin
copy 
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
copy 
2
4


3
9
15
21
https://ideone.com/YP70za
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!