fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fr(i, a, b) for (ll i = a; i < b; i++)
  4. #define mmst(i,a) memset(i,a,sizeof(i))
  5. #define all(i) i.begin(),i.end()
  6. #define allr(i) i.rbegin(),i.rend()
  7. #define caseout cout << "Case " << tc << ": ";
  8. #define fast                          \
  9.     ios_base::sync_with_stdio(false); \
  10.     cin.tie(NULL);                    \
  11.     cout.tie(NULL);
  12. #define yes cout << "YES" << endl
  13. #define no cout << "NO" << endl
  14. using namespace std;
  15. const ll mod=1e9+7;
  16.  
  17. void solve()
  18. {
  19.     string s1,s2;
  20.     cin>>s1>>s2;
  21.     ll dhv=0;
  22.     ll pow=1;
  23.     fr(i,0,s2.size()){
  24.         dhv+=((s2[i]-'a'+1)*pow)%mod;
  25.         pow=(pow*31)%mod;
  26.     }
  27.     ll pref[s1.size()+1];
  28.     ll currPow[s1.size()];
  29.     pref[0]=0;
  30.     pow=1;
  31.     fr(i,0,s1.size()){
  32.         pref[i+1]=(pref[i]+((s1[i]-'a'+1)*pow))%mod;
  33.         currPow[i]=pow;
  34.         pow=(pow*31)%mod;
  35.     }
  36.     ll sp=0,ep=s2.size();
  37.     vector<ll> ans;
  38.     while(ep<=s1.size()){
  39.         if((pref[ep]-pref[sp]+mod)%mod==((dhv*currPow[sp])%mod)){
  40.             ans.push_back(sp+1);
  41.         }
  42.         sp++;ep++;
  43.     }
  44.     // cout<<dhv<<endl;
  45.     if(ans.size()==0){
  46.         cout<<"Not Found"<<endl;
  47.         cout<<endl;
  48.         return;
  49.     }
  50.     cout<<ans.size()<<endl;
  51.     for(auto it: ans)cout<<it<<" ";cout<<endl;cout<<endl;
  52. }
  53. int main()
  54. {
  55.     fast ll T = 1;
  56.     cin >> T;
  57.     for (int tc = 1; tc <= T; tc++)
  58.     {
  59.         // cout<<"Case "<<tc<<": ";
  60.         solve();
  61.     }
  62. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
1
1
https://ideone.com/krtzgr
problem NAJPF, based on SPOJ submission 33002406 (CPP14-CLANG), 2024-05-04 05:23:09
language:
C++14 (clang 8.0)
created:
14 days 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!