fork download
copy 
  1. #include <iostream>
  2. #include <cstring> 
  3. using namespace std;
  4.  
  5.  
  6. int main(){
  7. 	int zf[1000000];
  8. 	char s[1000000];
  9.     scanf("%[^\n]%*c", s);
  10.     int n = strlen(s);
  11.     int right=0,left=0;
  12.  
  13.     for(int i=1; i < n; ++i){
  14.  
  15.             if(i<=right){
  16.         		zf[i]=min(right-i+1,zf[i-left]);
  17.             }
  18.             while(s[zf[i]]==s[zf[i]+i]){
  19.             	zf[i]++;
  20.             }
  21.             if(i+zf[i]-1>right){
  22.     	        left=i;
  23.                 right=i+zf[i]-1;
  24.             }
  25.     }
  26.  
  27.     for(int i=0; i < n; ++i){
  28.     	cout << zf[i] << " ";	
  29.     }
  30.  
  31. 	return 0; 
  32. }
Success #stdin #stdout 0s 8224KB
comments (?)
stdin
copy 
abaabaab
stdout
copy 
0 0 1 5 0 1 2 0
https://ideone.com/1Xc8GS
1309
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!