fork 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]]) return s[x];
  33.         return s[pos];
  34.     }
  35.  
  36.     activeLength -= (ends_at - curr -> st + 1);
  37.     activeNode = curr;
  38.     activeEdge = activeEdge + (ends_at - curr -> st + 1);
  39.     return getNext(x);
  40. }
  41.  
  42. bool walkdown(int x){
  43.     if(activeLength == 0) return false;
  44.     curr = activeNode -> child[s[activeEdge]];
  45.     int ends_at = (curr -> ed == last)? x : curr -> ed;
  46.     //cout << pos << " " << ends_at << endl;
  47.     if(ends_at - curr -> st < activeLength){
  48.         activeNode = curr;
  49.         activeLength -= (ends_at - curr -> st);
  50.         activeEdge = curr -> child[s[x]] -> st;
  51.     }
  52.     else activeLength ++;
  53. }
  54.  
  55. void startPhase(int j){
  56.     //cout << j << " " << remains << endl << endl;
  57.     node* lastNewNode = NULL;
  58.  
  59.     remains ++;
  60.     while(remains > 0){
  61.         //cout << remains << endl;
  62.         if(activeLength == 0){
  63.             if(roots -> child[s[j]]){
  64.                 activeNode = roots;
  65.                 activeEdge = roots->child[s[j]]->st;
  66.                 activeLength = 1;
  67.                 //cout << "here!" << endl;
  68.                 break;
  69.             }
  70.             else{
  71.                 roots -> child[s[j]] = new node(j, last);
  72.                 remains --;
  73.                 continue;
  74.             }
  75.         }
  76.         else{
  77.             curr = activeNode -> child[s[activeEdge]];
  78.             //cout << "    [" << curr -> st << " " << curr -> ed << "]\n";
  79.             char ch = getNext(j);
  80.  
  81.             if(ch == s[j]){
  82.                 //activeLength++;
  83.                 walkdown(j);
  84.                 break;
  85.             }
  86.             else{
  87.                 curr = activeNode -> child[s[activeEdge]];
  88.                 int pos = curr -> st + (activeLength );
  89.                 int ends_at = (curr -> ed == last)? j : curr -> ed;
  90.                 if(pos <= ends_at){
  91.                     node* interalNode = new node(curr -> st, pos-1);
  92.                     node* leaf = new node(j, last);
  93.                     curr -> st = pos;
  94.  
  95.                     interalNode -> child[s[j]] = leaf;
  96.                     interalNode -> child[s[pos]] = curr;
  97.                     activeNode -> child[s[interalNode -> st]] = interalNode;
  98.  
  99.                     if(lastNewNode != NULL){
  100.                         lastNewNode->suffixLink = interalNode;
  101.                         //cout << "here" << endl;
  102.                     }
  103.  
  104.                     lastNewNode = interalNode;
  105.                     interalNode -> suffixLink = roots;
  106.                 }
  107.                 else{
  108.                     curr -> child[s[j]] = new node(j, last);
  109.                     //curr -> suffixLink = roots;
  110.  
  111.                     if(lastNewNode != NULL)
  112.                         lastNewNode->suffixLink = curr;
  113.                     lastNewNode = curr;
  114.                 }
  115.  
  116.                 remains --;
  117.                 if(activeNode == roots){
  118.                     //cout << "here!\n";
  119.                     activeEdge ++;
  120.                     activeLength --;
  121.                 }
  122.                 else{
  123.                     activeNode = activeNode ->suffixLink;
  124.                     //cout << "[" << activeNode -> st << " " << activeNode -> ed << "]" << endl;
  125.                 }
  126.             }
  127.         }
  128.     }
  129. }
  130.  
  131. void print_dfs(node* root){
  132.     int enter = 0;
  133.     for(int j = 0; j < 256; j++)
  134.         if(root -> child[j]) print_dfs(root -> child[j]), enter++;
  135.     if(!enter) cout << "[" << root -> st << " " << root -> ed << "]  ";
  136. }
  137.  
  138. vector<int> ans;
  139.  
  140. void dfs(node* root, int cnt){
  141.     //cout << root->st << " " << cnt << endl;
  142.     if(root -> ed == last) root -> ed = s.length() - 1;
  143. 	int enter = 0;
  144. 	for(int j = 0; j < 256; j++)
  145. 		if(root -> child[j]) dfs(root -> child[j], cnt+(root->ed - root->st + 1)), enter++;
  146.     if(!enter) ans.push_back(s.length() - cnt - (root -> ed - root -> st));
  147. }
  148.  
  149. void build(){
  150.     roots = new node(-1, -1);
  151.     activeNode = roots;
  152.  
  153.     for(int j = 0; j < s.length(); j++)
  154.         startPhase(j);
  155.  
  156.     print_dfs(roots);
  157.     dfs(roots, 0);
  158. }
  159.  
  160. int main(){
  161. 	cin >> s;
  162. 	s += '$';
  163. 	//cout << s[47] << " " << s[34] << " " << s[2] << " " << s[24] << " " << s[55] << endl;
  164. 	build();
  165. 	for(int j = 1; j < ans.size(); j++)
  166.         cout << ans[j] << " ";
  167.     cout << endl;
  168. 	return 0;
  169. }
  170.  
Success #stdin #stdout 0s 4464KB
comments (?)
stdin
copy 
abaaaab
stdout
copy 
[7 100000009]  [5 100000009]  [6 100000009]  [6 100000009]  [7 100000009]  [2 100000009]  [7 100000009]  [2 100000009]  2 3 4 5 0 6 1
https://ideone.com/4oaxnR
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!