fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> z_function (string str) {
  9. 	int n = (int) str.length();
  10. 	vector<int> z (n);
  11. 	for (int i = 1, l = 0, r = 0; i < n; ++i) {
  12. 		if (i <= r)
  13. 			z[i] = min (r - i + 1, z[i - l]);
  14. 		while (i + z[i] < n && str[z[i]] == str[i + z[i]])
  15. 			++z[i];
  16. 		if (i + z[i] - 1 > r)
  17. 			l = i,  r = i + z[i] - 1;
  18. 	}
  19. 	return z;
  20. }
  21.  
  22. int main() {
  23.     cin.sync_with_stdio(0);
  24.     cin.tie(0);
  25.     string str;
  26.     cin >> str;
  27.     vector<int> z = z_function(str);
  28.     for (size_t i = 0; i < str.size(); ++i)
  29.        cout << z[i] << (char)32;
  30. }
  31.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
abracadabra
stdout
copy 
0 0 0 1 0 1 0 4 0 0 1
https://ideone.com/SDq5hC
language:
C++ (gcc 8.3)
created:
3 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!