fork(2) 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.         if(t[t[c].link].leaf)
  44.             t[c].e_link = t[c].link;
  45.         else
  46.             t[c].e_link = t[t[c].link].e_link;
  47.     }
  48.     return t[c].link;
  49. }
  50. int go(int c,char ch){
  51.     int v = ch-'a';
  52.     if(t[c].go[v]==-1){
  53.         if(t[c].next[v]!=-1)
  54.             t[c].go[v] = t[c].next[v];
  55.         else
  56.             t[c].go[v] = (c==0)? 0: go(get_link(c),ch);
  57.     }
  58.     return t[c].go[v];
  59. }
  60. void search(char s[]){
  61.     int n = strlen(s);
  62.     int c = 0;
  63.     for(int i=0;i<n;i++){
  64.         c = go(c,s[i]);
  65.         int cc = c;
  66.         while(cc!=-1 && t[cc].leaf){
  67.             cout<<i<<" "<<t[cc].id<<endl; // end position and string id
  68.             cc = t[cc].e_link;
  69.         }
  70.     }
  71. }
  72. signed main()
  73. {
  74.     string arr[3] = {"a", "aa", "aaa"};
  75.     for(int i=0;i<3;i++)
  76.         add_string(arr[i],i);
  77.     char s[] = "aaaaa";
  78.     search(s);
  79.     return 0;
  80. }
Success #stdin #stdout 0s 4156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
1 1
2 2
3 2
3 1
3 0
4 2
4 1
4 0
https://ideone.com/1nQiE3
language:
C++14 (gcc 8.3)
created:
5 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!