fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define mp make_pair
  5. #define f0(n) for(int i=0;i<n;i++)
  6. #define ms(x) memset(x,0,sizeof(x))
  7. #define ins insert
  8. #define IOS ios::sync_with_stdio(false);
  9. using namespace std;
  10. const long long MOD = 1000000007;
  11. template<typename T>inline T Bigmod(T base, T power, T MOD){
  12.     T ret=1;
  13.     while(power)
  14.     {
  15.         if(power & 1)ret=(ret*base)%MOD;
  16.         base=(base*base)%MOD;
  17.         power>>=1;
  18.     }
  19.     return ret;
  20. }
  21.  
  22. bool sortinrev(const pair<int,int> &a,
  23.                const pair<int,int> &b)
  24. {
  25.        return (a.first > b.first);
  26. }
  27. vector<int>computeLcp(string pat){
  28.     int m = pat.size();
  29.     vector<int>lcp(m);
  30.     lcp[0] = 0;
  31.     int len = 0;
  32.     int i = 1;
  33.     while(i<m)
  34.     {
  35.         if(pat[len]==pat[i])
  36.         {
  37.             len++;
  38.             lcp[i] = len;
  39.             i++;
  40.         }
  41.         else{
  42.             if(len!=0)
  43.             {
  44.                 len = lcp[len-1];
  45.             }
  46.             else
  47.             {
  48.                 lcp[i] = 0;
  49.                 i++;
  50.             }
  51.  
  52.         }
  53.     }
  54.     return lcp;
  55. }
  56. int kmp(string txt,string pat)
  57. {
  58.     vector<int>lcp=computeLcp(pat);
  59.     int n=txt.size(),m = pat.size();
  60.     int i = 0,j = 0;
  61.     int cnt = 0;
  62.     while(i<n)
  63.     {
  64.         if(pat[j]==txt[i])
  65.         {
  66.             i++;j++;
  67.         }
  68.         if(j==m)
  69.         {
  70.             cnt++;
  71.             j = lcp[j-1];
  72.         }
  73.         else if(i<n && pat[j]!=txt[i])
  74.         {
  75.             if(j!=0)
  76.             {
  77.                 j = lcp[j-1];
  78.             }
  79.             else i++;
  80.         }
  81.     }
  82.     return cnt++;
  83. }
  84. int main()
  85. {
  86. 	IOS
  87.     string s,t;
  88.     cin>>s;
  89.     vector<int>lcp;
  90.     lcp=computeLcp(s);
  91.     for(int i=0;i<lcp.size();i++)
  92.         cout << lcp[i]<<" ";
  93.     cout << endl;
  94.     return 0;
  95. }
  96.  
  97.  
  98.  
  99.  
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
hohoho
stdout
copy 
0 0 1 2 3 4
https://ideone.com/fR6v9Y
language:
C++14 (gcc 8.3)
created:
4 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!