fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int mod=1e9+7,mod1=998244353;
  5. signed main()
  6. {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(0);
  9.     cout.tie(0);
  10.     string A,B;
  11.     cin>>A>>B;
  12.     bool K[A.size()+1];
  13.     if(A.size()>=B.size()){
  14.         int dp[A.size()+1];
  15.         dp[0]=0;
  16.         for(int a=1;a<=A.size();a++){
  17.             dp[a]=(dp[a-1]*26+A[a-1]-94+mod)%mod;
  18.         }
  19.         int dp1[B.size()+1];
  20.         dp1[0]=0;
  21.         int sum=1;
  22.         for(int a=0;a<B.size();a++){
  23.             sum*=26;
  24.             sum%=mod;
  25.         }
  26.         for(int a=1;a<=B.size();a++){
  27.             dp1[a]=(dp1[a-1]*26+B[a-1]-94+mod)%mod;
  28.         }
  29.         /*for(int a=1;a<=A.size();a++){
  30.             cout<<dp[a]<<"\n";
  31.         }*/
  32.         int m=0;
  33.         for(int a=B.size();a<=A.size();a++){
  34.             if((dp[a]%mod-(dp[a-B.size()]*sum)%mod+mod)%mod==dp1[B.size()]){
  35.                 K[a-B.size()+1]=1;
  36.             }
  37.             // cout<<(dp[a]-dp[a-B.size()]*sum)%mod<<" "<<dp1[B.size()]<<"\n";
  38.         }
  39.         dp[0]=0;
  40.         for(int a=1;a<=A.size();a++){
  41.             dp[a]=(dp[a-1]*26+A[a-1]-94+mod1)%mod1;
  42.         }
  43.         dp1[0]=0;
  44.         sum=1;
  45.         for(int a=0;a<B.size();a++){
  46.             sum*=26;
  47.             sum%=mod1;
  48.         }
  49.         for(int a=1;a<=B.size();a++){
  50.             dp1[a]=(dp1[a-1]*26+B[a-1]-94+mod1)%mod1;
  51.         }
  52.         /*for(int a=1;a<=A.size();a++){
  53.             cout<<dp[a]<<"\n";
  54.         }*/
  55.  
  56.         for(int a=B.size();a<=A.size();a++){
  57.             if((dp[a]%mod1-(dp[a-B.size()]*sum)%mod1+mod1)%mod1==dp1[B.size()]){
  58.                 if(K[a-B.size()+1]) cout<<a-B.size()+1<<" ";
  59.             }
  60.             // cout<<(dp[a]-dp[a-B.size()]*sum)%mod<<" "<<dp1[B.size()]<<"\n";
  61.         }
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/KCy1TZ
language:
C++14 (gcc 8.3)
created:
23 hours 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!