fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7. #define ld double
  8. const int md = 1e9+7;
  9.  
  10. const int K = 26;
  11. struct node{
  12.     int next[K],go[K],link = -1,e_link = -1;
  13.     bool leaf = 0;
  14.     char pch;
  15.     int p = -1;
  16.     int id;
  17.     node(int p = -1,char ch = '#'):p(p),pch(ch){
  18.         fill(next,next+K,-1);
  19.         fill(go,go+K,-1);
  20.     }
  21. };
  22. vector<node> t(1);
  23. void add_string(string s,int id){
  24.     int c = 0;
  25.     for(char ch: s){
  26.         int v = ch-'a';
  27.         if(t[c].next[v]==-1){
  28.             t[c].next[v] = t.size();
  29.             t.emplace_back(c,ch);
  30.         }
  31.         c = t[c].next[v];
  32.     }
  33.     t[c].leaf = 1;
  34.     t[c].id = id;
  35. }
  36. int go(int c,char ch);
  37. int get_link(int c){
  38.     if(t[c].link==-1){
  39.         if(c==0 || t[c].p==0)
  40.             t[c].link = 0;
  41.         else
  42.             t[c].link = go(get_link(t[c].p),t[c].pch);
  43.         get_link(t[c].link);
  44.         if(t[t[c].link].leaf)
  45.             t[c].e_link = t[c].link;
  46.         else
  47.             t[c].e_link = t[t[c].link].e_link;
  48.     }
  49.     return t[c].link;
  50. }
  51. int go(int c,char ch){
  52.     int v = ch-'a';
  53.     if(t[c].go[v]==-1){
  54.         if(t[c].next[v]!=-1)
  55.             t[c].go[v] = t[c].next[v];
  56.         else
  57.             t[c].go[v] = (c==0)? 0: go(get_link(c),ch);
  58.     }
  59.     return t[c].go[v];
  60. }
  61. void search(char s[]){
  62.     int n = strlen(s);
  63.     int c = 0;
  64.     for(int i=0;i<n;i++){
  65.         c = go(c,s[i]);
  66.         int cc = c;
  67.         while(cc!=-1){
  68.             if(t[c].leaf)
  69.             cout<<i<<" "<<t[cc].id<<endl; // end position and string id
  70.             cc = t[cc].e_link;
  71.         }
  72.     }
  73. }
  74. signed main()
  75. {
  76.     string arr[3] = {"a", "aa", "aaa"};
  77.     for(int i=0;i<3;i++)
  78.         add_string(arr[i],i);
  79.     for(int i = 1; i < t.size(); i++) // 
  80.         get_link(i); // 
  81.     char s[] = "aaaaa";
  82.     search(s);
  83.     return 0;
  84. }
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
1 1
1 0
2 2
2 1
2 0
3 2
3 1
3 0
4 2
4 1
4 0
https://ideone.com/6FDgeP
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!