fork download
copy 
  1. class DSU:
  2.     def __init__(self, n):
  3.         self.parent = list(range(n))
  4.         self.rank = [1] * n
  5.         self.components = n
  6.  
  7.     def find(self, x):
  8.         if self.parent[x] != x:
  9.             self.parent[x] = self.find(self.parent[x])
  10.         return self.parent[x]
  11.  
  12.     def union(self, x, y):
  13.         rootX = self.find(x)
  14.         rootY = self.find(y)
  15.         if rootX != rootY:
  16.             if self.rank[rootX] > self.rank[rootY]:
  17.                 self.parent[rootY] = rootX
  18.             elif self.rank[rootX] < self.rank[rootY]:
  19.                 self.parent[rootX] = rootY
  20.             else:
  21.                 self.parent[rootY] = rootX
  22.                 self.rank[rootX] += 1
  23.             self.components -= 1
  24.         return self.components
  25.  
  26. def minimum_string_length_for_components(s):
  27.     n = len(s)
  28.     results = [0] * n
  29.     for k in range(1, n + 1):
  30.         dsu = DSU(n)
  31.         substring_lengths = {}
  32.  
  33.         for length in range(1, n + 1):
  34.             for start in range(n - length + 1):
  35.                 substr = s[start:start + length]
  36.                 if substr not in substring_lengths:
  37.                     substring_lengths[substr] = length
  38.  
  39.                 for i in range(start, start + length - 1):
  40.                     dsu.union(i, i + 1)
  41.  
  42.         for substr in sorted(substring_lengths.keys(), key=lambda x: substring_lengths[x]):
  43.             length = substring_lengths[substr]
  44.             current_components = dsu.components
  45.             if current_components <= k:
  46.                 results[k - 1] = length
  47.                 break
  48.             for start in range(n - length + 1):
  49.                 if s[start:start + length] == substr:
  50.                     for i in range(start, start + length - 1):
  51.                         dsu.union(i, i + 1)
  52.  
  53.     return results
  54.  
  55. # Read input
  56. import sys
  57. input = sys.stdin.read
  58. data = input().strip()
  59.  
  60. # Calculate and print results
  61. results = minimum_string_length_for_components(data)
  62. print(" ".join(map(str, results)))
  63.  
Success #stdin #stdout 0.03s 9640KB
comments (?)
stdin
copy 
aabcabcaa
stdout
copy 
1 1 1 1 1 1 1 1 1
https://ideone.com/aPPN7X
language:
Python 3 (python  3.9.5)
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!