fork(1) download
  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] = {"his","her","she"};
  75. for(int i=0;i<3;i++)
  76. add_string(arr[i],i);
  77. char s[10] = "hishershe";
  78. search(s);
  79. return 0;
  80. }
Success #stdin #stdout 0s 4492KB
stdin
Standard input is empty
stdout
2 0
4 2
5 1
8 2