include cstdio include cstdlib include iostream include vector include

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <stack>
#include <sstream>
#include <queue>
#include <iomanip>
#include <cmath>
#include <unordered_map>
using namespace std;
#define forn(i, n) for(int i = 0; i < (n); ++i)
#define PATH "D:\\QtProjects\\olymp\\"
#define debug(x) cerr << "DEBUG " << #x << ": " << x << endl;
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 8002;
int h[N];
int ppow[N];
const int P = 263;
inline void init(){
ppow[0] = -1;
for (int i = 1; i < N; ++i)
ppow[i] = ppow[i - 1] * P;
}
inline void makeh(const string& s){
h[0] = 0;
forn(i, (int)s.size()) h[i+1] = h[i] * P + s[i];
}
inline int geth(const int l, const int r){
return h[r] + h[l] * ppow[r-l];
}
int k;
int pos;
string s;
inline int LCP(int l, int r){
l = l + pos;
r = r + pos;
if (s[l] != s[r]) return 0;
int xl = 1;
int xr = min(pos + k - l, pos + k - r);
while (xr - xl > 1){
int m = (xl + xr) / 2;
int h1 = geth(l, l + m);
int h2 = geth(r, r + m);
if (h1 == h2) xl = m;
else xr = m;
}
if (geth(l, l + xr) == geth(r, r + xr)) return xr;
else return xl;
}
inline int cmp(const int& l, const int& r){
int lcp = LCP(l, r);
if (l + lcp == k) return true;
if (r + lcp == k) return false;
return s[pos + l + lcp] < s[pos + r + lcp];
}
int suf[N];
inline void lolsort(){
for (int i = 0; suf[0] != 0; ++i){
if (suf[i] == 0) {
while (i != 0) {
suf[i] = suf[i - 1];
--i;
}
suf[0] = 0;
}
}
for (int i = 1; i < k; ++i) --suf[i];
suf[0] = k - 1;
for (int i = 1; i + 1 < k; ++i) if (!cmp(suf[i], suf[i+1])){
swap(suf[i], suf[i+1]);
}
bool swapped = true;
while(swapped){
swapped = false;
for (int i = 0; i + 1 < k; ++i) if (!cmp(suf[i], suf[i+1])){
swapped = true;
swap(suf[i], suf[i+1]);
}
}
//sort(suf, suf + k, cmp);
}
int main(){
//freopen(PATH"input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
init();
s.reserve(8001);
cin >> k;
getline(cin, s); getline(cin, s);
int n = (int)s.size();
s += s;
makeh(s);
forn(i, k) suf[i] = i;
sort(suf, suf + k, cmp);
for (pos = 0; pos < n; ){
int cnt = k - suf[0];
for (int i = 1; i < k; ++i){
int lcp = LCP(suf[i-1], suf[i]);
cnt += k - suf[i] - lcp;
}
cout << cnt << ' ';
if (++pos < n) {
lolsort();
}
}
cout << endl;
return 0;
}