include iostream include algorithm include string include vector using

 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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
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<int> 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;
}