fork download
copy 
  1. // █▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
  2. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  3. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  4. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄▄█▀███▀▀▀▀▀██▀▀▀▀▄▄▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  5. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄█▀▀░░▄▄██▀▀░░░▄█▀░░░░░░░▄█▀█▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  6. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄█▀▀░░░▄▄█▀█▀░░░░▄█░░░░░░░░░░░▀█░▀███▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░█
  7. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄█▀░▄▄░▄█▀░░▄▀░░░░▄█░░░░░░░░░░░░░▀█░░█▄░▀█▄░░░░░░░░░░░░░░░░░░░░░░░░█
  8. // █░░░░░░░░░░░░░▄▄▄▄▄▄▄░░░░░░░░░░█▀▄█▀▀░█▀░░▄█▀░░░░█▀░░░░░░░░░░░░░░░█░░░█░░░░▀█░░░░░░░░░░░░░░░░░░░░░░█
  9. // █░░░░░░░░░░░░▀█▄▄▄▄▄█▀█▄░░░░░▄▀▄█▀░░░█░░░▄█░░░░░░█░░░░░░░░░░░░░░░░█░░░█░░░░░░█▄░░░░░░░░░░░░░░░░░░░░█
  10. // █░░░░░░░░░░░▄▄▀▀░░░░▀▀░▀█░░▄███▀░░░░░█░░░█░░░░░░░█░░░░░░░░▄░░░░░░░█░░░█░░░░░█░▀█▄░░░░░░░░░░░░░░░░░░█
  11. // █░░░░░░░░░▄█▀▄█▀░░▄█░░░░▀█▄▀▄█░░▄░░░░▀░░░░░░░░░░▄█░░░░░░░░█░░░░░░░█░░░█░░░░░█░░░█▄░░░░░░░░░░░░░░░░░█
  12. // █░░░░░░░░██▄██▀░░█▀░░▄▄▄▀▄██▀░░░█░░▄░░░░░░░░░░░░█▀░░░░░░░█▀░░░░░░██░░░█░░░░░█░░░░█▀▄░░░░░░░░░░░░░░░█
  13. // █░░░░░░░░▀░░█▀░▄██▄▄█▀░░▄██░░░░░█░░█░░░░░▄░░░░░░▀█░░░░░░░█░░░░░░▄█░░░░█░░░░░█░░░░░░▀█▄░░░░░░░░░░░░░█
  14. // █░░░░░░░░░░░█▄█▀░█▀░░░░▄█▀░░░░░░█░░█░░░░░█░░░░░░░█░░░░░░░█░░░░░▄█░░░░▄█░░░░░█░░░░░░░░▀▄▄▄█▀▀█▄░░░░░█
  15. // █░░░░░░░░░░░▀▄▄██▀▄▄▄▀▀▀█░░░░░░░█░░█░░░░░█░▄▄▄▄▄▄▀▀▀▀▀▀▀▀█▄▄▄▄▄█▄▄░░░█░░░░░░█░░░▄░░░░░█░░▄▄▄░█░░░░░█
  16. // █░░░░░░░░░░▄█▀▄█░▀█░░░░█▀░░░░░░░█░░█░█░░░███▄█▀██████▀▀▀▀▀░░░░░░░▀▀█▄█░░░░░▄█░░░█░░░░░█░░░▀████░░░░█
  17. // █░░░░░░░░░█▀░█▀░░░█░░░░█░░░░░░░░█░░█░█▄░█▀░░░░░▀███▄▀▀░░░░░░░░░▀▀▀█▄██▄▄▄░░█░░░░█░░░░░█░░░░░▀▀█▄░░░█
  18. // █░░░░░░░░▄█▄░░░▄▄█░░░░░█░░░░░░░░█░░█▀▀▀▀░░░░░░░██▄██░░░░░░░░░░░░█▀███▀▀▄█▀▀▀█▄▄░█░░░░░▀█░░██▄░░█▄░░█
  19. // █░░░░░░░█▀▄██▀██░░░░░░░█░░░░░░░░█▄░▀█░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄███░░░▀█▄░░░▀▀█░░░█░░█░░▀█▀▀█▄█░░█
  20. // █░░░░░░░█░▀░░▄█░░░░░░░░█░░░░░░░░░█▄░▀█▄░░░▄▄▄▄▄▄▄▄▄▄░░░░░█▀░░░░░▀▀▀▀░░░░░░▀█░░░▄█░░▄▀░░█░▄▄█░░░▀▀░░█
  21. // █░░░░░░▄▀░░▄█▀░░░░░░░█▀█░░░░░▄░░░░█▄░░▀█▀▀▀░░░░░░░░░░░░░░░░░░░░▀█▄▄▄░░░░░░░░█▄░█░░▄█░░░██▀░░░░░░░░░█
  22. // █░░░░░██░▄█▀█░░░░░░░░█░▀▄░░░░░█░░░▀██▄▄▀█▄░░░░░░░░░░░░░▀▀░░░░░░░░░░▀▀█▄▄░░░░░██▀░▄█░░░███░░░░░░░░░░█
  23. // █░░░░▄█▀█▀░▄▀░░░░░░░░█░░█░░░░░░█▄░░▀▄░░▀▀██░░░░░░░▄▄▄▄▄▄▄▄▄░░░░░░░░░░░░▀▀▄▄▄▄█▄▄▀▀░░░░█░▀▄░░░░░░░░░█
  24. // █░░░░█░░░▄█▀░░░░░░░░░█▄░█▄░░░░░░▀█▄░▀█░░░░░▄▀▀▄░█▀▀░░░░░░░▀▀▀▀█▄░░░░░░░░░░░░█▀█░░░░░░░█░░█░░░░░░░░░█
  25. // █░░░░▀█░▄▀█░░░░░░░░░░░▀█▄██░░░░░░░░████▄░░█▀░░░▀░░░░░░░░░░░░░░░▀▀▄░░░░░░░░░░░░█░░░░░░█▀░░█▄░░░░░░░░█
  26. // █░░░░░█▄▀░█░░░░░░░░░░░░█░░░░░░█▀█▄░█▄░░▀▀░█░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░██▀█░░░▀▄░░░█░░░░░░░░█
  27. // █░░░░█▀░░░█▄▄░░░░░░░░░░█░░░██▄█░░▀█▄▀▄░░░░█▄░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░▄▄▀░▄█▀▀▀█░▀█▄░█░░░░░░░░█
  28. // █░░░░▀▄▄▄▄█▄▀█░░░░░░▄▄▄██▄▄█▄██▄░░██▄██░░░░█░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░█░░▄▀░░█▀█░░░░░█░░░░░░░░█
  29. // █░░░░░▀█▀░░░▄█▄█▀▀▀▀▀░░░░░░░█░██░░█░█▄▄▀▀▀▀▀▀▀▀▄▄▄▄▄▄░░░░░░░░░░░█▀░░░██▄░░█▀▄█░░▄█░░█░░░▄▄█░░░░░░░░█
  30. // █░░░░░░█▄░▄█▀░░░░░░░░░░░░░░░░█░█▄░█░█░▀█░░░░░░░░░░░░█▀▀▀▀▀▀▄▄▄▄██░░░█▀░█░█▀█▀░▄▄▀░▄█▀░░▀▀░█░░░░░░░░█
  31. // █░░░░░░░█▀▀░░░░░░░░░░░░░░░░░░█▄░█░█░█░░█░░░░░░░░░░░░█░░░░▄▄▄░░█░▀▀▀▀█░░██▀░░▄█▀░▄█▀░▀█░░░░█░░░░░░░░█
  32. // █░░░░░░█░░░░░░▄▄████████▄░░░░░█░░░█▄█░░█░░░░░░░░░░░░█░░░░███░░█░░░░░█░▄█▀░░░░░▄██▄░░░▀▀░░█░░░░░░░░░█
  33. // █░░░░░░█░░░░░█████████████▄░░░▀█░░░░▀░░▀▄░░░░░░░░░░░█░░░░░░░░░█░░░░░█▄▀░░░░▄░░█░░░▀█▄▄█▀▀░░░░░░░░░░█
  34. // █░░░░░░█▄░░░░▀███████▀▀▀▀▀█▄░░░▀▄░░░░░░░█░░░░░░░░░░░█░░░░░░░░░█░░░░█▀▀░░▄█▀░░█░░░░░██░░░░░░░░░░░░░░█
  35. // █░░░░░░░█░░░░░░███▀░░░░░░░░▀▄░░░▀█░░░░░░█░░░░░░░░░░░█░░░░░░░░░█░░░█▀░░░█▀░░░█▀░░░░▄█░░░░░░░░░░░░░░░█
  36. // █░░░░░░░▀▄░░░░░██░░░░░░░░░░░░▀░░░█░░░░░░▀█░░▄▄░░░░░░█░░░░░░░░▄█░░░█░░▄█░░░░░█░░░░░█░░░░░░░░░░░░░░░░█
  37. // █░░░░░░░░▀█░░▄█▀░░░░░░░░░░░░░░░░▄█░░░░░░░▀█░▀▀▀▀▀█▄▄█▄▄▄▄▄▄▄▄█▄▄▄█▀░░█░░░░░▄█░░░░░█░░░░░░░░░░░░░░░░█
  38. // █░░░░░░░░░█░▄▀░░░░░░░░░░░░░░░▄█▀▀▀█▄░░░░░░▀█░░░░░░▀▀██████████████░░█▀░░░░░█░░░░░█▀░░░░░░░░░░░░░░░░█
  39. // █░░░░░░░░░██▀░░░░░░░░░░░░░░▄██░░░░░█▄░░░░░░█░░░░░░░░█░░░░░▀▀▀▀▀█▀█░░█░░░░░░█░░░░░█░░░░░░░░░░░░░░░░░█
  40. // █░░░░░░░░░██▀░░░░░░░░░░░░░░██░░░░░░░█▄░░░░░█░░░░░░░░█░░░░░░░░░░█░▀█▄█░░░░░░███▄░░▀▄░░░░░░░░░░░░░░░░█
  41. // █░░░░░░░░░██▄▄░░░░░░░░░░░░▄██░░░░░░░░▀█▄░▄█▀░░░░░░░░█░░░░░░░░░▄█░░█▄░░░░░░░██░▀█▄░▀█░░░░░░░░░░░░░░░█
  42. // █░░░░░░░▄██▀░▀█▄░░░░░░░░░░██▀░░░░░░░░░░▀▀█░░░░░░░░░▄▀░░░░░░░░▄█░░░██▄░░░░░▄██░░░█▄░▀█░░░░░░░░░░░░░░█
  43. // █░░░░░░░██▀░░░░▀▀▄▄░░░░░░██▀█▄░░░░░░░░░░░▀▀▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄░░█░░░▄▀░█░░░░░▀░█░░░░▀▄░▀█░░░░░░░░░░░░░█
  44. // █░░░░░░██▀░░░░░░░░▀█▄░░▄██▀░░░▀▄░░░░░░░░░░░░▀██████████████████▄█▀░░▀█░░░░░░█░░░░░█▄░▀▄░░░░░░░░░░░░█
  45. // █░░░░░░██░░░░░░░░░░░▀█▄██▀░░░░░░█▄░░░░░░░░░░░▀███████████████████░░░░▀█░░░░█▀░░░░░░█░░█░░░░░░░░░░░░█
  46. // █░░░░░██░░░░░░░░░░░░░░██▀░░░░░░░░▀█▄░░░░░░░░░░▀█████████████████▀░░░░░▀█░░▄█░░░░░░░█▄░░█░░░░░░░░░░░█
  47. // █░░░░▄█░░░░░░░░░░░░░▄██▀░░░░░░░░░░░▀█▄░░░░░░░░░▀████████████████░░░░░░░▀▄█▀░░░░░░░█▀█░░▀▄░░░░░░░░░░█
  48. // █░░░░█░░░░░░░░░░░░▄▄██▀░░░░░░░░░░░░░░█▄░░░░░░░░░░██▀▀▀▀▀▀██▀▀▀█▀░░░░░░░░█▀░░░░░░░▄█░█▄░░▀█▄░░░░░░░░█
  49. // █░░░░█░░░░░░░░░░░███▀░░░░░░░░░░░░░░░░░█▄░░░░░░░░░░█▄░░░░░█░░░░█░░░░░░░▄█▀░░░░░░░▄█░░░█░░░░▀▄░░░░░░░█
  50. // █▄▄▄▄█▄▄▄▄▄▄▄▄▄▄██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄█▄▄▄▄█▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄█▄▄▄▄█▄▄▄▄▄██▄▄▄▄▄▄█
  51. #include<bits/stdc++.h>
  52. using namespace std;
  53. string a,b;
  54. int cnta[26];
  55. int cnt[200001][26];
  56. long long hsh[200001];
  57. long long mod=1e9+11;
  58. long long base=31;
  59. long long mu[200001];
  60. long long gethsh(int l,int r){
  61.     return (hsh[r]-hsh[l-1]*mu[r-l+1]+mod*mod)%mod;
  62. }
  63. set<long long>s;
  64. void process(){
  65.     int ans=0;
  66.     for(int i=1;i+a.size()-1<=b.size();i++){
  67.         bool ok=1;
  68.         for(int j=0;j<26;j++){
  69.             if(cnt[i+a.size()-1][j]-cnt[i-1][j]!=cnta[j]){
  70.                 ok=0;
  71.                 break;
  72.             }
  73.         }
  74.         if(ok){
  75.             s.insert(gethsh(i,i+a.size()-1));
  76.         }
  77.     }
  78.     cout<<s.size();
  79. }      
  80. void init(){
  81.     cin>>a>>b;
  82.     mu[0]=1;
  83.     for(int i=0;i<a.size();i++){
  84.         cnta[a[i]-'a']++;
  85.     }
  86.     for(int i=1;i<=b.size();i++){
  87.         hsh[i]=(hsh[i-1]*base+b[i-1]-'a')%mod;
  88.         mu[i]=(mu[i-1]*base)%mod;
  89.         for(int j=0;j<26;j++)cnt[i][j]=cnt[i-1][j];
  90.         cnt[i][b[i-1]-'a']++;
  91.     }
  92. }   
  93. int main(){
  94.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  95.     #define NAME "nazunasdish"
  96.     if(fopen(NAME".inp","r")){
  97.         freopen(NAME".inp","r",stdin);
  98.         freopen(NAME".ans","w",stdout);
  99.     }
  100.     clock_t beg=clock();
  101.     init();
  102.     process();
  103.     cerr<<double(clock()-beg)/CLOCKS_PER_SEC;
  104. }
  105.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/PRUgR5
language:
C++14 (gcc 8.3)
created:
7 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!