#include #include #include #include using namespace std; typedef long long ll; const ll P = 257; //const ll M = 1000000009; const int N = 8100; ll ppow[N]; ll h[N]; inline void init(){ ppow[0] = -1; for (int i = 1; i < N; ++i) { ppow[i] = ppow[i - 1] * P;// % M; } } inline void makehashes(const string& s){ h[0] = 0; for (int i = 0; i < s.size(); ++i){ h[i + 1] = (h[i] * P + s[i]);// % M; } } inline ll gethash(int l, int r){ return (h[r] + h[l] * ppow[r - l]);// % M; } int k, n; string ss; inline int LCP(const int& l, const int& r){ int xl = 0; int xr = min(k, min(n - l, n - r)); while (xr - xl > 1){ int m = (xl + xr) / 2; ll h1 = gethash(l, l + m); ll h2 = gethash(r, r + m); if (h1 == h2) xl = m; else xr = m; } return ((gethash(l, l + xr) == gethash(r, r + xr))? xr : xl); } inline bool cmp(const int& l, const int& r){ int lcp = LCP(l, r); if (l + lcp == n) return true; if (r + lcp == k) return false; return ss[l + lcp] < ss[r + lcp]; } int main(){ ios_base::sync_with_stdio(false); //ss = "abaccc"; //k = 3; cin >> k; getline(cin, ss); getline(cin, ss); int n = ss.size(); ss += ss; makehashes(ss); init(); vector sm(k); for (int j = 0; j < k; ++j) sm[j] = j; for (pos = 0; pos < n; ++pos){ sort(sm.begin(), sm.end(), cmp); int ans = k - sm[0]; for (int j = 1; j < k; ++j) ans += k - sm[j] - LCP(sm[j], sm[j - 1]); cout << ans << ' '; } return 0; }