fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void getZarr(string str, int Z[]);
  5.  
  6. void search(string text, string pattern)
  7. {
  8.     string concat = pattern + "$" + text;
  9.     int l = concat.length();
  10.     int Z[l];
  11.     getZarr(concat, Z);
  12.     int cnt=0;
  13.     for (int i = 0; i < l; ++i)
  14.     {
  15.         if (Z[i] == pattern.length())
  16.         {
  17.           cnt++;
  18.         }
  19.     }
  20.     cout<<cnt<<endl;
  21. }
  22.  
  23. void getZarr(string str, int Z[])
  24. {
  25.     int n = str.length();
  26.     int L, R, k;
  27.     L = R = 0;
  28.     for (int i = 1; i < n; ++i)
  29.     {
  30.         if (i > R)
  31.         {
  32.             L = R = i;
  33.             while (R<n && str[R-L] == str[R])
  34.             {
  35.               R++;
  36.           Z[i] = R-L;
  37.             }
  38.             R--;
  39.         }
  40.         else
  41.         {
  42.             k = i-L;
  43.             if (Z[k] < R-i+1)
  44.             {
  45.               Z[i] = Z[k];
  46.             }
  47.             else
  48.             {
  49.                 L = i;
  50.                 while (R<n && str[R-L] == str[R])
  51.                 {
  52.                   R++;
  53.               Z[i] = R-L;
  54.                 }
  55.                 R--;
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     string text;
  64.     string pattern;
  65.     cin>>pattern;
  66.     cin>>text;
  67.     search(text, pattern);
  68.     return 0;
  69. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/1eykjC
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!