fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int last = 1e8 + 9;
  6.  
  7. struct node{
  8.     int st, ed;
  9.     node* child[256];
  10.     node* suffixLink;
  11.  
  12.     node(int l, int r) : st(l), ed(r){
  13.         for(int j = 0; j < 256; j++)
  14.             child[j] = NULL;
  15.         suffixLink = NULL;
  16.     }
  17. };
  18.  
  19. node *roots, *activeNode, *curr;
  20.  
  21. int activeLength = 0, activeEdge = -1, remains = 0;
  22.  
  23. string s;
  24.  
  25. char getNext(int x){
  26.     curr = activeNode -> child[s[activeEdge]];
  27.     int pos = curr -> st + activeLength;
  28.     int ends_at = (curr -> ed == last)? x : curr -> ed;
  29.     if(pos <= ends_at) return s[pos];
  30.  
  31.     if(pos == ends_at + 1){
  32.         if(curr -> child[s[x]]){
  33.             activeNode = curr;
  34.             activeLength = 0;
  35.             curr = curr -> child[s[x]];
  36.             activeEdge = curr -> st;
  37.             return s[x];
  38.         }
  39.         return s[pos];
  40.     }
  41.  
  42.     activeLength -= (curr -> ed - curr -> st + 1);
  43.     activeNode = curr;
  44.     activeEdge = ends_at + 1;
  45.     curr = curr -> child[s[ends_at + 1]];
  46.     return getNext(x);
  47. }
  48.  
  49. bool walkdown(int x){
  50.     if(activeLength == 0) return false;
  51.     curr = activeNode -> child[s[activeEdge]];
  52.     int pos = curr -> st + activeLength - 1;
  53.     int ends_at = (curr -> ed == last)? x : curr -> ed;
  54.     //cout << pos << " " << ends_at << endl;
  55.     if(pos <= ends_at) return false;
  56.  
  57.     activeNode = curr;
  58.     activeLength -= (ends_at - curr -> st + 1);
  59.     activeEdge = ends_at + 1;
  60.     curr = curr -> child[activeEdge];
  61.     return true;
  62. }
  63.  
  64. void startPhase(int j){
  65.     //cout << j << " " << remains << endl << endl;
  66.     node* lastNewNode = NULL;
  67.  
  68.     remains ++;
  69.     while(remains > 0){
  70.         //cout << remains << endl;
  71.         if(activeLength == 0){
  72.             if(roots -> child[s[j]]){
  73.                 activeNode = roots;
  74.                 activeEdge = roots->child[s[j]]->st;
  75.                 activeLength = 1;
  76.                 //cout << "here!" << endl;
  77.                 walkdown(j);
  78.                 //cout << "here!" << endl;
  79.                 break;
  80.             }
  81.             else{
  82.                 roots -> child[s[j]] = new node(j, last);
  83.                 remains --;
  84.                 continue;
  85.             }
  86.         }
  87.         else{
  88.             curr = activeNode -> child[s[activeEdge]];
  89.             //cout << "    [" << curr -> st << " " << curr -> ed << "]\n";
  90.             char ch = getNext(j);
  91.  
  92.             if(ch == s[j]){
  93.                 activeLength++;
  94.                 walkdown(j);
  95.                 break;
  96.             }
  97.             else{
  98.                 int pos = curr -> st + (activeLength );
  99.                 int ends_at = (curr -> ed == last)? j : curr -> ed;
  100.                 if(pos <= ends_at){
  101.                     node* interalNode = new node(curr -> st, pos-1);
  102.                     node* leaf = new node(j, last);
  103.                     curr -> st = pos;
  104.  
  105.                     interalNode -> child[s[j]] = leaf;
  106.                     interalNode -> child[s[pos]] = curr;
  107.                     activeNode -> child[s[interalNode -> st]] = interalNode;
  108.  
  109.                     if(lastNewNode != NULL){
  110.                         lastNewNode->suffixLink = interalNode;
  111.                         //cout << "here" << endl;
  112.                     }
  113.  
  114.                     lastNewNode = interalNode;
  115.                     interalNode -> suffixLink = roots;
  116.                 }
  117.                 else{
  118.                     curr -> child[s[j]] = new node(j, last);
  119.                     //curr -> suffixLink = roots;
  120.  
  121.                     if(lastNewNode != NULL)
  122.                         lastNewNode->suffixLink = curr;
  123.                     lastNewNode = curr;
  124.                 }
  125.  
  126.                 remains --;
  127.                 if(activeNode == roots){
  128.                     //cout << "here!\n";
  129.                     activeEdge ++;
  130.                     activeLength --;
  131.                 }
  132.                 else{
  133.                     activeNode = activeNode ->suffixLink;
  134.                     //cout << "[" << activeNode -> st << " " << activeNode -> ed << "]" << endl;
  135.                 }
  136.             }
  137.         }
  138.     }
  139. }
  140.  
  141. void print_dfs(node* root){
  142.     int enter = 0;
  143.     for(int j = 0; j < 256; j++)
  144.         if(root -> child[j]) print_dfs(root -> child[j]), enter++;
  145.     if(!enter) cout << "[" << root -> st << " " << root -> ed << "]  ";
  146. }
  147.  
  148. vector<int> ans;
  149.  
  150. void dfs(node* root, int cnt){
  151.     //cout << root->st << " " << cnt << endl;
  152.     if(root -> ed == last) root -> ed = s.length() - 1;
  153. 	int enter = 0;
  154. 	for(int j = 0; j < 256; j++)
  155. 		if(root -> child[j]) dfs(root -> child[j], cnt+(root->ed - root->st + 1)), enter++;
  156.     if(!enter) ans.push_back(s.length() - cnt - (root -> ed - root -> st));
  157. }
  158.  
  159. void build(){
  160.     roots = new node(-1, -1);
  161.     activeNode = roots;
  162.  
  163.     for(int j = 0; j < s.length(); j++)
  164.         startPhase(j);
  165.  
  166.     //print_dfs(roots);
  167.     dfs(roots, 0);
  168. }
  169.  
  170. int main(){
  171. 	cin >> s;
  172. 	s += '$';
  173. 	//cout << s[47] << " " << s[34] << " " << s[2] << " " << s[24] << " " << s[55] << endl;
  174. 	build();
  175. 	for(int j = 1; j < ans.size(); j++)
  176.         cout << ans[j] << " ";
  177.     cout << endl;
  178. 	return 0;
  179. }
  180.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
ykbbvmbsrmuikxwmrkjmvhpbsektyplycmaxzdpsqjcciyoalxoghejbktukl
stdout
copy 
47 34 2 55 23 6 3 42 43 32 37 53 25 51 52 21 11 44 54 41 18 1 17 59 56 26 12 60 48 30 33 5 15 9 19 46 50 22 29 38 40 16 8 24 39 7 57 27 10 58 20 4 14 49 13 35 31 0 45 28 36
https://ideone.com/ZUfpWX
language:
C++14 (gcc 8.3)
created:
6 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!