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.                 if(lastNewNode != NULL)
  85.                     lastNewNode ->suffixLink = activeNode;
  86.                 break;
  87.             }
  88.             else{
  89.                 curr = activeNode -> child[s[activeEdge]];
  90.                 int pos = curr -> st + (activeLength );
  91.                 int ends_at = (curr -> ed == last)? j : curr -> ed;
  92.                 if(pos <= ends_at){
  93.                     node* interalNode = new node(curr -> st, pos-1);
  94.                     node* leaf = new node(j, last);
  95.                     curr -> st = pos;
  96.  
  97.                     interalNode -> child[s[j]] = leaf;
  98.                     interalNode -> child[s[pos]] = curr;
  99.                     activeNode -> child[s[interalNode -> st]] = interalNode;
  100.  
  101.                     if(lastNewNode != NULL){
  102.                         lastNewNode->suffixLink = interalNode;
  103.                         //cout << "here" << endl;
  104.                     }
  105.  
  106.                     lastNewNode = interalNode;
  107.                     interalNode -> suffixLink = roots;
  108.                 }
  109.                 else{
  110.                     curr -> child[s[j]] = new node(j, last);
  111.                     //curr -> suffixLink = roots;
  112.  
  113.                     if(lastNewNode != NULL)
  114.                         lastNewNode->suffixLink = curr;
  115.                     lastNewNode = curr;
  116.                 }
  117.  
  118.                 remains --;
  119.                 if(activeNode == roots){
  120.                     //cout << "here!\n";
  121.                     activeEdge ++;
  122.                     activeLength --;
  123.                 }
  124.                 else{
  125.                     activeNode = activeNode ->suffixLink;
  126.                     //cout << "[" << activeNode -> st << " " << activeNode -> ed << "]" << endl;
  127.                 }
  128.             }
  129.         }
  130.     }
  131. }
  132.  
  133. void print_dfs(node* root){
  134.     int enter = 0;
  135.     for(int j = 0; j < 256; j++)
  136.         if(root -> child[j]) print_dfs(root -> child[j]), enter++;
  137.     if(!enter) cout << "[" << root -> st << " " << root -> ed << "]  ";
  138. }
  139.  
  140. vector<int> ans;
  141.  
  142. void dfs(node* root, int cnt){
  143.     //cout << root->st << " " << cnt << endl;
  144.     if(root -> ed == last) root -> ed = s.length() - 1;
  145. 	int enter = 0;
  146. 	for(int j = 0; j < 256; j++)
  147. 		if(root -> child[j]) dfs(root -> child[j], cnt+(root->ed - root->st + 1)), enter++;
  148.     if(!enter) ans.push_back(s.length() - cnt - (root -> ed - root -> st));
  149. }
  150.  
  151. void build(){
  152.     roots = new node(-1, -1);
  153.     activeNode = roots;
  154.  
  155.     for(int j = 0; j < s.length(); j++)
  156.         startPhase(j);
  157.  
  158.     print_dfs(roots);
  159.     dfs(roots, 0);
  160. }
  161.  
  162. int main(){
  163. 	cin >> s;
  164. 	s += '$';
  165. 	//cout << s[47] << " " << s[34] << " " << s[2] << " " << s[24] << " " << s[55] << endl;
  166. 	build();
  167. 	for(int j = 1; j < ans.size(); j++)
  168.         cout << ans[j] << " ";
  169.     cout << endl;
  170. 	return 0;
  171. }
  172.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
aaabaaaaa
stdout
copy 
[9 100000009]  [9 100000009]  [9 100000009]  [9 100000009]  [9 100000009]  [8 100000009]  [3 100000009]  [3 100000009]  [3 100000009]  [3 100000009]  8 7 6 5 4 0 1 2 3
https://ideone.com/4GxpU2
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!