fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define endl "\n"
  5.  
  6. struct node{
  7. 	map<char,int> nxt;
  8. 	int link = 0;
  9. 	vector<int> out;
  10. };
  11.  
  12. void add(const string &s, int id, vector<node> &t){
  13. 	int v = 0;
  14. 	for(int i = 0; i < s.size(); i++){
  15. 		char c = s[i];
  16. 		if(!t[v].nxt.count(c)){
  17. 			t[v].nxt[c] = t.size();
  18. 			t.emplace_back();
  19. 		}
  20. 		v = t[v].nxt[c];
  21. 	}
  22. 	t[v].out.push_back(id);
  23. }
  24.  
  25. void build(vector<node> &t){
  26. 	queue<int> q;
  27. 	for (auto &p : t[0].nxt) {
  28. 	    t[p.second].link = 0;
  29. 	    q.push(p.second);
  30. 	}
  31. 	while (!q.empty()) {
  32. 	    int v = q.front(); q.pop();
  33. 	    for (auto &p : t[v].nxt) {
  34. 	        char c = p.first;
  35. 	        int u = p.second;
  36. 	        int j = t[v].link;
  37. 	        while (j && !t[j].nxt.count(c))
  38. 	            j = t[j].link;
  39. 	        if (t[j].nxt.count(c))
  40. 	            j = t[j].nxt[c];
  41. 	        t[u].link = j;
  42. 	        for (int x : t[j].out)
  43. 	            t[u].out.push_back(x);
  44. 	        q.push(u);
  45. 	    }
  46. 	}
  47. }
  48.  
  49. void search(const string &s, const vector<int> &L, vector<vector<int>> &res, vector<node> &t){
  50. 	int v = 0;
  51. 	for(int i = 0; i < s.size(); i++){
  52. 		char c = s[i];
  53. 		while(v && !t[v].nxt.count(c)) v = t[v].link;
  54. 		if(t[v].nxt.count(c)) v = t[v].nxt[c];
  55. 		for(int id : t[v].out) res[id].push_back(i - L[id] + 1);
  56. 	}	
  57. }
  58.  
  59. signed main(){
  60. 	ios_base::sync_with_stdio(0);
  61. 	cin.tie(0);cout.tie(0);
  62. 	int n;
  63. 	while(cin >> n){
  64. 		string tmp; getline(cin, tmp);
  65. 		vector<string> P(n);
  66. 		for(int i = 0; i < n; i++)getline(cin, P[i]);
  67. 		string T; getline(cin, T);
  68. 		vector<node> t;
  69. 		t.emplace_back();
  70. 		vector<int> L(n);
  71. 		for(int i = 0; i < n; i++){
  72. 			L[i] = P[i].size();
  73. 			add(P[i], i, t);
  74. 		}
  75. 		build(t);
  76. 		vector<vector<int>> occ(n);
  77. 		search(T,L,occ,t);
  78. 		for(int i = 0; i < n; i++){
  79. 			for(int j = 0; j < occ[i].size(); j++){
  80. 				if(j)cout << ' ';
  81. 				cout << occ[i][j];
  82. 			}
  83. 			cout << endl;
  84. 		}
  85. 	}
  86. 	return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
p
pup
Popup
2
You
peek a boo
you speek a bootiful language
4
anas
ana
an
a
bananananaspaj
stdout
copy 
2 4
2

5
7
1 3 5 7
1 3 5 7
1 3 5 7 9 12
https://ideone.com/nGOcwF
language:
C++14 (gcc 8.3)
created:
1 day 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!