fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb push_back
  17.  
  18. #define totalone(mask) __builtin_popcount(mask)
  19. #define chkbit(mask,bit) (mask&(1LL << bit))
  20. #define setbit(mask,bit) (mask|(1LL << bit))
  21. #define cngbit(mask,bit) (mask^(1LL << bit))
  22.  
  23. #define en "\n"
  24. #define dbg(x) cerr<<#x<<" is : "<<x<<en;
  25. #define yes cout<<"YES\n"
  26. #define no cout<<"NO\n"
  27. #define report cout<<-1<<en
  28. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  29. #define sqr(n) (1LL*(n)*(n))
  30. #define vag(a,b) ((a + b - 1)/b)
  31. #define coutv(v) for(auto i: v) cout<<i<<" ";cout<<en;
  32. #define cinv(v) for(auto &i: v) cin >> i;
  33.  
  34. #define MAXN 200010
  35. #define inf 1e6+5
  36. const int mod = 1e9 + 7;
  37.  
  38.  
  39. // Print how many times a pattern occurs in the string "s"
  40. // and print their starting index as well
  41.  
  42. vector<int> lps_maker(string pat)
  43. {
  44.     // abacaba
  45.     int n = pat.size();
  46.     vector<int> lps(n, 0);
  47.  
  48.     for (int i = 1; i < n; i++)
  49.     {
  50.         int len = lps[i - 1];
  51.         while (len > 0 && pat[i] != pat[len]) {
  52.             len = lps[len - 1];
  53.         }
  54.         if (pat[i] == pat[len]) {
  55.             len++;
  56.         }
  57.         lps[i] = len;
  58.     }
  59.  
  60.     return lps;
  61.  
  62. }
  63.  
  64. void kmp(string s, string pat)
  65. {
  66.     vector<int>lps = lps_maker(pat);
  67.     int i = 0, j = 0;
  68.  
  69.     vector<int>v;
  70.  
  71.     while (i < (int)s.size())
  72.     {
  73.         if (s[i] == pat[j]) {
  74.             j++; i++;
  75.         }
  76.         else {
  77.             if (j > 0)
  78.                 j = lps[j - 1];
  79.             else i++;
  80.         }
  81.  
  82.         if (j == (int)pat.size())
  83.         {
  84.             v.pb(i - (int)pat.size());
  85.             j = lps[j - 1];
  86.         }
  87.     }
  88.  
  89.     if ((int)v.size() == 0 ) cout << "No match found\n";
  90.     else coutv(v);
  91.  
  92. }
  93. void solve()
  94. {
  95.     string s, pat;
  96.     cin >> s >> pat;
  97.     kmp(s, pat);
  98. }
  99. int main()
  100. {
  101.     IOS;
  102.     ll t;
  103.     t = 1;
  104.     // cin >> t;
  105.  
  106.     int c = 0;
  107.     while ( t-- )
  108.     {
  109.         // cout<<"Case "<<++c<<": ";
  110.         solve();
  111.     }
  112.     return 0;
  113. }
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No match found
https://ideone.com/8DBWzn
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!