

#include <bits/stdc++.h>
using
namespace
std;
int
dp[1001][1001][26];
int
ans[1001][26];
void
preprocess(string s)
{
int
n = s.length();
memset
(dp, 0,
sizeof
(dp));
for
(
int
i = 1; i <= n; i++) {
dp[i][0][s[i - 1] -
'a'
] = 1;
}
for
(
int
i = 1; i <= n; i++) {
for
(
int
j = 0; j <= i; j++) {
for
(
int
k = 0; k < 26; k++) {
if
(s[i - 1] ==
char
(k +
'a'
))
dp[i][j][k] = dp[i - 1][j][k] + 1;
else
if
(j != 0)
dp[i][j][k] = dp[i - 1][j - 1][k] + 1;
}
}
}
memset
(ans, 0,
sizeof
(ans));
for
(
int
i = 1; i <= n; i++) {
for
(
int
j = 0; j < 26; j++) {
for
(
int
k = 1; k <= n; k++)
ans[i][j] = max(ans[i][j], dp[k][i][j]);
}
}
}
vector<
int
> query(string s,
vector<pair<
int
,
char
> >& queries)
{
preprocess(s);
vector<
int
> res;
for
(
auto
u : queries) {
res.push_back(ans[u.first][u.second -
'a'
]);
}
return
res;
}
int
main()
{
string s =
"yamatonadeshiko"
;
vector<pair<
int
,
char
> > queries;
queries.push_back({ 1,
'a'
});
queries.push_back({ 2,
'a'
});
queries.push_back({ 3,
'a'
});
queries.push_back({ 4,
'a'
});
queries.push_back({ 5,
'a'
});
queries.push_back({ 1,
'b'
});
queries.push_back({ 2,
'b'
});
queries.push_back({ 3,
'b'
});
queries.push_back({ 4,
'b'
});
queries.push_back({ 5,
'b'
});
vector<
int
> sol = query(s, queries);
for
(
int
x : sol)
cout << x <<
" "
;
return
0;
}