fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. class UnionFind {
  9. private:
  10.     vector<int> parent, rank;
  11.     int components;
  12.  
  13. public:
  14.     UnionFind(int n) : parent(n), rank(n, 0), components(n) {
  15.         for (int i = 0; i < n; i++) parent[i] = i;
  16.     }
  17.  
  18.     int find(int x) {
  19.         if (parent[x] != x) {
  20.             parent[x] = find(parent[x]);
  21.         }
  22.         return parent[x];
  23.     }
  24.  
  25.     bool unite(int x, int y) {
  26.         int px = find(x), py = find(y);
  27.         if (px == py) return false;
  28.  
  29.         components--;
  30.         if (rank[px] < rank[py]) {
  31.             parent[px] = py;
  32.         } else if (rank[px] > rank[py]) {
  33.             parent[py] = px;
  34.         } else {
  35.             parent[py] = px;
  36.             rank[px]++;
  37.         }
  38.         return true;
  39.     }
  40.  
  41.     int getComponents() {
  42.         return components;
  43.     }
  44. };
  45.  
  46. vector<int> solve(const string& s) {
  47.     int n = s.length();
  48.     vector<int> result(n, 0);
  49.  
  50.     // Pour chaque longueur possible de substring
  51.     for (int len = 1; len <= n; len++) {
  52.         // Pour chaque position de début possible
  53.         set<string> patterns;
  54.         for (int i = 0; i + len <= n; i++) {
  55.             patterns.insert(s.substr(i, len));
  56.         }
  57.  
  58.         // Pour chaque pattern possible
  59.         for (const string& pattern : patterns) {
  60.             UnionFind uf(n);
  61.  
  62.             // Chercher toutes les occurrences du pattern
  63.             for (int i = 0; i + len <= n; i++) {
  64.                 if (s.substr(i, len) == pattern) {
  65.                     // Connecter les îles consécutives dans cette occurrence
  66.                     for (int j = i; j < i + len - 1; j++) {
  67.                         uf.unite(j, j + 1);
  68.                     }
  69.                 }
  70.             }
  71.  
  72.             int components = uf.getComponents();
  73.             if (result[components - 1] == 0 || len < result[components - 1]) {
  74.                 result[components - 1] = len;
  75.             }
  76.         }
  77.     }
  78.  
  79.     return result;
  80. }
  81.  
  82. int main() {
  83.     ios_base::sync_with_stdio(false);
  84.     cin.tie(nullptr);
  85.  
  86.     string s;
  87.     cin >> s;
  88.  
  89.     vector<int> result = solve(s);
  90.  
  91.     for (int i = 0; i < result.size(); i++) {
  92.         if (i > 0) cout << " ";
  93.         cout << result[i];
  94.     }
  95.     cout << "\n";
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
aabcabcaa
stdout
copy 
9 8 4 6 3 4 2 0 1
https://ideone.com/LKu8sN
language:
C++ (gcc 8.3)
created:
5 days 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!