# 2023/3/17 做题技巧总结()-其他

## 2023/3/17 做题技巧总结()

### T3

AC代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define MAXN 100000
#define MAXM 20
#define INF 0x3f3f3f3f

class suffix_array{
private:
template <typename type>
int* first_sort (type *s, type *end) {
pair <type, int> *barrel_sort = new pair<type, int>[end - s];
int *barrel = new int[end - s];

for (type *i = s; i < end; i ++) {
barrel_sort[i - s] = make_pair (*i, int (i - s));
}
sort (barrel_sort, barrel_sort + int(end - s));
for (pair <type, int> *i = barrel_sort; i < barrel_sort + int(end - s); i ++) {
barrel[i - barrel_sort] = i->second;
}

return barrel;
}
int query_rank (int *loc, int *end) {
return loc >= end ? -1 : *loc;
}
public:
template <typename type>
int* Sort (type *s, type *end) {
int *barrel = first_sort (s, end);
int *barrel_end = new int[end - s];
int *temporary_barrel = new int[end - s];
int *rank = new int[end - s];
int num = 1;

*(rank + *barrel) = 0;
for (int *i = barrel + 1; i < barrel + int(end - s); i ++) {
if (*(s + *i) != *(s + *(i - 1))) {
barrel_end[num - 1] = i - barrel - 1;
num ++;
}
*(rank + *i) = num - 1;
}
barrel_end[num - 1] = int(end - s) - 1;
for (int len = 1; len < end - s; len <<= 1) {
for (type *i = s; i < end; i ++) {
temporary_barrel[i - s] = barrel[i - s];
}
for (type *i = end - 1; i >= s; i --) {
if (temporary_barrel[i - s] - len >= 0) {
barrel[barrel_end[rank[temporary_barrel[i - s] - len]] --] = temporary_barrel[i - s] - len;
}
}
for (int i = 0; i < len; i ++) {
barrel[barrel_end[rank[i + int(end - s) - len]] --] = i + int(end - s) - len;
}
num = 1;
for (int *i = barrel + 1; i < end - s + barrel; i ++) {
if (*(rank + *i) != *(rank + *(i - 1)) || query_rank (rank + *i + len, rank + int(end - s)) != query_rank (rank + *(i - 1) + len, rank + int(end - s))) {
barrel_end[num - 1] = i - barrel - 1;
num ++;
}
}
barrel_end[num - 1] = int(end - s) - 1;
for (int t = 0, i = 0; t < num; t ++) {
while (i <= barrel_end[t]) {
rank[barrel[i]] = t;
i ++;
}
}
}

return rank;
}
}sa;
struct node {
node *sonl = 0, *sonr = 0;
int v = 0;
}*rt[MAXN + 5];
struct trie {
trie *next[26] = {};
pair<int, int> v;
}*root;

char c[MAXN +5];
int sloc[MAXN + 5];
int st[MAXN + 5][MAXM + 5];
int Log[MAXN + 5];
unsigned long long b[MAXN + 5], Hash[MAXN + 5];
map <unsigned long long, pair<int, int> > Map;

long long find (int l, int r) {
if (l > r) {
return 0;
}

return Hash[r] - Hash[l - 1] * b[r - l + 1];
}
int find_st (int l, int r) {
if (l > r) {
return INF;
}
else {
int u = Log[r - l + 1];

return min (st[l][u], st[r - (1 << u) + 1][u]);
}
}

node* change (node *p, int l, int r, int loc, int v) {
node *new_p = new node;

if (p) {
*new_p = *p;
}
new_p->v += v;
if (l == r) {
return new_p;
}

int mid = (l + r) >> 1;

if (loc <= mid) {
new_p->sonl = change (new_p->sonl, l, mid, loc, v);
}
else {
new_p->sonr = change (new_p->sonr, mid + 1, r, loc, v);
}

return new_p;
}

int ask (node *p, int l, int r, int h) {
if (!p || p->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask (p->sonr, mid + 1, r, h);
}
else {
int v = ask (p->sonl, l, mid, h);

if (~v) {
return v;
}
else {
return ask (p->sonr, mid + 1, r, h);
}
}
}
int ask (node *p1, node *p2, int l, int r, int h) {
if (!p2) {
return ask (p1, l, r, h);
}
if (!p1 || p1->v - p2->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask (p1->sonr, p2->sonr, mid + 1, r, h);
}
else {
int v = ask (p1->sonl, p2->sonl, l, mid, h);

if (~v) {
return v;
}
else {
return ask (p1->sonr, p2->sonr, mid + 1, r, h);
}
}
}

int main () {
freopen ("string.in", "r", stdin);
freopen ("string.out", "w", stdout);

int n, m;
int Q;

scanf ("%d %d", &n, &m);
scanf ("%s", c + 1);
b[0] = 1;
for (int i = 1; i <= n; i ++) {
b[i] = b[i - 1] * 13331;
Hash[i] = Hash[i - 1] * 13331 + c[i];
}
Log[0] = 0;
Log[1] = 0;
for (int i = 2; i <= n; i ++) {
Log[i] = Log[i >> 1] + 1;
}
Q = max(1, int(sqrt (n * Log[n])));

int *s = sa.Sort (c + 1, c + 1 + n);

for (int i = 0; i < n; i ++) {
sloc[s[i]] = i;
}
for (int i = 1; i <= n; i ++) {
rt[i] = change (rt[i - 1], 1, n, sloc[i - 1] + 1, 1);
}
for (int i = 1; i < n; i ++) {
int l = 0, r = min (n - sloc[i - 1], n - sloc[i]);

while (l < r) {
int mid = (l + r + 1) >> 1;

if (find (sloc[i - 1] + 1, sloc[i - 1] + mid) == find (sloc[i] + 1, sloc[i] + mid)) {
l = mid;
}
else {
r = mid - 1;
}
}
st[i][0] = l;
}
for (int i = 1; i <= Log[n - 1]; i ++) {
for (int j = 1; j < n - (1 << i) + 1; j ++) {
st[j][i] = min (st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
root = new trie;
for (int i = 1; i <= n; i ++) {
trie *p = root;

if (!p->next[c[i] - 'a']) {
p->next[c[i] - 'a'] = new trie;
}
p = p->next[c[i] - 'a'];
for (int j = 2; j <= Q && j <= n - i + 1; j ++) {
if (!p->next[c[i + j - 1] - 'a']) {
p->next[c[i + j - 1] - 'a'] = new trie;
}
p = p->next[c[i + j - 1] - 'a'];
if (p->v.second < i) {
p->v.first ++;
p->v.second = i + j - 2;
}
}
}
for (int i = 1; i <= m; i ++) {
int l, r;

scanf ("%d %d", &l, &r);
if (l == r) {
printf ("-1\n");

continue;
}
if (r - l + 1 > Q) {
int hl = 0, hr = s[l - 1];
int tl = 0, tr = n - s[l - 1] - 1;

while (hl < hr) {
int mid = (hl + hr + 1) >> 1;

if (find_st (s[l - 1] - mid + 1, s[l - 1]) >= r - l + 1) {
hl = mid;
}
else {
hr = mid - 1;
}
}
while (tl < tr) {
int mid = (tl + tr + 1) >> 1;

if (find_st (s[l - 1] + 1, s[l - 1] + mid) >= r - l + 1) {
tl = mid;
}
else {
tr = mid - 1;
}
}

int h = 0;
int sum = 0;

while (h <= n) {
h = ask (rt[s[l - 1] + tr + 1], rt[s[l - 1] - hl], 1, n, h);
if (!(~h)) {
break;
}
h += (r - l);
sum ++;
}
printf ("%d\n", sum);
}
else {
trie *p = root;

for (int j = l; j <= r; j ++) {
p = p->next[c[j] - 'a'];
}
printf ("%d\n", p->v.first);
}
}
}


// ubsan: undefined
// accoders
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define MAXN 100000
#define MAXM 20
#define INF 0x3f3f3f3f

class suffix_array {
private:
template <typename type>
int *first_sort(type *s, type *end) {
pair<type, int> *barrel_sort = new pair<type, int>[end - s];
int *barrel = new int[end - s];

for (type *i = s; i < end; i++) {
barrel_sort[i - s] = make_pair(*i, int(i - s));
}
sort(barrel_sort, barrel_sort + int(end - s));
for (pair<type, int> *i = barrel_sort; i < barrel_sort + int(end - s); i++) {
barrel[i - barrel_sort] = i->second;
}

return barrel;
}
int query_rank(int *loc, int *end) { return loc >= end ? -1 : *loc; }

public:
template <typename type>
int *Sort(type *s, type *end) {
int *barrel = first_sort(s, end);
int *barrel_end = new int[end - s];
int *temporary_barrel = new int[end - s];
int *rank = new int[end - s];
int num = 1;

*(rank + *barrel) = 0;
for (int *i = barrel + 1; i < barrel + int(end - s); i++) {
if (*(s + *i) != *(s + *(i - 1))) {
barrel_end[num - 1] = i - barrel - 1;
num++;
}
*(rank + *i) = num - 1;
}
barrel_end[num - 1] = int(end - s) - 1;
for (int len = 1; len < end - s; len <<= 1) {
for (type *i = s; i < end; i++) {
temporary_barrel[i - s] = barrel[i - s];
}
for (type *i = end - 1; i >= s; i--) {
if (temporary_barrel[i - s] - len >= 0) {
barrel[barrel_end[rank[temporary_barrel[i - s] - len]]--] = temporary_barrel[i - s] - len;
}
}
for (int i = 0; i < len; i++) {
barrel[barrel_end[rank[i + int(end - s) - len]]--] = i + int(end - s) - len;
}
num = 1;
for (int *i = barrel + 1; i < end - s + barrel; i++) {
if (*(rank + *i) != *(rank + *(i - 1)) ||
query_rank(rank + *i + len, rank + int(end - s)) !=
query_rank(rank + *(i - 1) + len, rank + int(end - s))) {
barrel_end[num - 1] = i - barrel - 1;
num++;
}
}
barrel_end[num - 1] = int(end - s) - 1;
for (int t = 0, i = 0; t < num; t++) {
while (i <= barrel_end[t]) {
rank[barrel[i]] = t;
i++;
}
}
}

return rank;
}
} sa;
struct node {
node *sonl = 0, *sonr = 0;
int v = 0;
} * rt[MAXN + 5];

char c[MAXN + 5];
int sloc[MAXN + 5];
int st[MAXN + 5][MAXM + 5];
int Log[MAXN + 5];
unsigned long long b[MAXN + 5], Hash[MAXN + 5];
map<unsigned long long, pair<int, int> > Map;

long long find(int l, int r) {
if (l > r) {
return 0;
}

return Hash[r] - Hash[l - 1] * b[r - l + 1];
}
int find_st(int l, int r) {
if (l > r) {
return INF;
} else {
int u = Log[r - l + 1];

return min(st[l][u], st[r - (1 << u) + 1][u]);
}
}
node *change(node *p, int l, int r, int loc, int v) {
node *new_p = new node;

if (p) {
*new_p = *p;
}
new_p->v += v;
if (l == r) {
return new_p;
}

int mid = (l + r) >> 1;

if (loc <= mid) {
new_p->sonl = change(new_p->sonl, l, mid, loc, v);
} else {
new_p->sonr = change(new_p->sonr, mid + 1, r, loc, v);
}

return new_p;
}

int ask(node *p, int l, int r, int h) {
if (!p || p->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask(p->sonr, mid + 1, r, h);
} else {
int v = ask(p->sonl, l, mid, h);

if (~v) {
return v;
} else {
return ask(p->sonr, mid + 1, r, h);
}
}
}
int ask(node *p1, node *p2, int l, int r, int h) {
if (!p2) {
}
if (!p1 || p1->v - p2->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask(p1->sonr, p2->sonr, mid + 1, r, h);
} else {
int v = ask(p1->sonl, p2->sonl, l, mid, h);

if (~v) {
return v;
} else {
return ask(p1->sonr, p2->sonr, mid + 1, r, h);
}
}
}

int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);

int n, m;
int Q;

scanf("%d %d", &n, &m);
Q = sqrt(n);
scanf("%s", c + 1);
b[0] = 1;
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] * 13331;
Hash[i] = Hash[i - 1] * 13331 + c[i];
}
Log[0] = 0;
Log[1] = 0;
for (int i = 2; i <= n; i++) {
Log[i] = Log[i >> 1] + 1;
}

int *s = sa.Sort(c + 1, c + 1 + n);

for (int i = 0; i < n; i++) {
sloc[s[i]] = i;
}
for (int i = 1; i <= n; i++) {
rt[i] = change(rt[i - 1], 1, n, sloc[i - 1] + 1, 1);
}
for (int i = 1; i < n; i++) {
int l = 0, r = min(n - sloc[i - 1], n - sloc[i]);

while (l < r) {
int mid = (l + r + 1) >> 1;

if (find(sloc[i - 1] + 1, sloc[i - 1] + mid) == find(sloc[i] + 1, sloc[i] + mid)) {
l = mid;
} else {
r = mid - 1;
}
}
st[i][0] = l;
}
for (int i = 1; i <= Log[n - 1]; i++) {
for (int j = 1; j < n - (1 << i) + 1; j++) {
st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= Q && j <= n - i + 1; j++) {
unsigned long long v = find(i, i + j - 1);
map<unsigned long long, pair<int, int> >::iterator it = Map.find(v);

if (it == Map.end()) {
Map.insert(make_pair(v, make_pair(1, i + j - 2)));
} else if (it->second.second < i) {
it->second.first++;
it->second.second = i + j - 2;
}
}
}
for (int i = 1; i <= m; i++) {
int l, r;

scanf("%d %d", &l, &r);
if (l == r) {
printf("-1\n");

continue;
}
if (r - l + 1 > Q) {
int hl = 0, hr = s[l - 1];
int tl = 0, tr = n - s[l - 1] - 1;

while (hl < hr) {
int mid = (hl + hr + 1) >> 1;

if (find_st(s[l - 1] - mid + 1, s[l - 1]) >= r - l + 1) {
hl = mid;
} else {
hr = mid - 1;
}
}
while (tl < tr) {
int mid = (tl + tr + 1) >> 1;

if (find_st(s[l - 1] + 1, s[l - 1] + mid) >= r - l + 1) {
tl = mid;
} else {
tr = mid - 1;
}
}

int h = 0;
int sum = 0;

while (h <= n) {
h = ask(rt[s[l - 1] + tr + 1], rt[s[l - 1] - hl], 1, n, h);
if (!(~h)) {
break;
}
h += (r - l);
sum++;
}
printf("%d\n", sum);
} else {
printf("%d\n", Map[find(l, r)].first);
}
}
}


————————

### T3

AC代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define MAXN 100000
#define MAXM 20
#define INF 0x3f3f3f3f

class suffix_array{
private:
template <typename type>
int* first_sort (type *s, type *end) {
pair <type, int> *barrel_sort = new pair<type, int>[end - s];
int *barrel = new int[end - s];

for (type *i = s; i < end; i ++) {
barrel_sort[i - s] = make_pair (*i, int (i - s));
}
sort (barrel_sort, barrel_sort + int(end - s));
for (pair <type, int> *i = barrel_sort; i < barrel_sort + int(end - s); i ++) {
barrel[i - barrel_sort] = i->second;
}

return barrel;
}
int query_rank (int *loc, int *end) {
return loc >= end ? -1 : *loc;
}
public:
template <typename type>
int* Sort (type *s, type *end) {
int *barrel = first_sort (s, end);
int *barrel_end = new int[end - s];
int *temporary_barrel = new int[end - s];
int *rank = new int[end - s];
int num = 1;

*(rank + *barrel) = 0;
for (int *i = barrel + 1; i < barrel + int(end - s); i ++) {
if (*(s + *i) != *(s + *(i - 1))) {
barrel_end[num - 1] = i - barrel - 1;
num ++;
}
*(rank + *i) = num - 1;
}
barrel_end[num - 1] = int(end - s) - 1;
for (int len = 1; len < end - s; len <<= 1) {
for (type *i = s; i < end; i ++) {
temporary_barrel[i - s] = barrel[i - s];
}
for (type *i = end - 1; i >= s; i --) {
if (temporary_barrel[i - s] - len >= 0) {
barrel[barrel_end[rank[temporary_barrel[i - s] - len]] --] = temporary_barrel[i - s] - len;
}
}
for (int i = 0; i < len; i ++) {
barrel[barrel_end[rank[i + int(end - s) - len]] --] = i + int(end - s) - len;
}
num = 1;
for (int *i = barrel + 1; i < end - s + barrel; i ++) {
if (*(rank + *i) != *(rank + *(i - 1)) || query_rank (rank + *i + len, rank + int(end - s)) != query_rank (rank + *(i - 1) + len, rank + int(end - s))) {
barrel_end[num - 1] = i - barrel - 1;
num ++;
}
}
barrel_end[num - 1] = int(end - s) - 1;
for (int t = 0, i = 0; t < num; t ++) {
while (i <= barrel_end[t]) {
rank[barrel[i]] = t;
i ++;
}
}
}

return rank;
}
}sa;
struct node {
node *sonl = 0, *sonr = 0;
int v = 0;
}*rt[MAXN + 5];
struct trie {
trie *next[26] = {};
pair<int, int> v;
}*root;

char c[MAXN +5];
int sloc[MAXN + 5];
int st[MAXN + 5][MAXM + 5];
int Log[MAXN + 5];
unsigned long long b[MAXN + 5], Hash[MAXN + 5];
map <unsigned long long, pair<int, int> > Map;

long long find (int l, int r) {
if (l > r) {
return 0;
}

return Hash[r] - Hash[l - 1] * b[r - l + 1];
}
int find_st (int l, int r) {
if (l > r) {
return INF;
}
else {
int u = Log[r - l + 1];

return min (st[l][u], st[r - (1 << u) + 1][u]);
}
}

node* change (node *p, int l, int r, int loc, int v) {
node *new_p = new node;

if (p) {
*new_p = *p;
}
new_p->v += v;
if (l == r) {
return new_p;
}

int mid = (l + r) >> 1;

if (loc <= mid) {
new_p->sonl = change (new_p->sonl, l, mid, loc, v);
}
else {
new_p->sonr = change (new_p->sonr, mid + 1, r, loc, v);
}

return new_p;
}

int ask (node *p, int l, int r, int h) {
if (!p || p->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask (p->sonr, mid + 1, r, h);
}
else {
int v = ask (p->sonl, l, mid, h);

if (~v) {
return v;
}
else {
return ask (p->sonr, mid + 1, r, h);
}
}
}
int ask (node *p1, node *p2, int l, int r, int h) {
if (!p2) {
return ask (p1, l, r, h);
}
if (!p1 || p1->v - p2->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask (p1->sonr, p2->sonr, mid + 1, r, h);
}
else {
int v = ask (p1->sonl, p2->sonl, l, mid, h);

if (~v) {
return v;
}
else {
return ask (p1->sonr, p2->sonr, mid + 1, r, h);
}
}
}

int main () {
freopen ("string.in", "r", stdin);
freopen ("string.out", "w", stdout);

int n, m;
int Q;

scanf ("%d %d", &n, &m);
scanf ("%s", c + 1);
b[0] = 1;
for (int i = 1; i <= n; i ++) {
b[i] = b[i - 1] * 13331;
Hash[i] = Hash[i - 1] * 13331 + c[i];
}
Log[0] = 0;
Log[1] = 0;
for (int i = 2; i <= n; i ++) {
Log[i] = Log[i >> 1] + 1;
}
Q = max(1, int(sqrt (n * Log[n])));

int *s = sa.Sort (c + 1, c + 1 + n);

for (int i = 0; i < n; i ++) {
sloc[s[i]] = i;
}
for (int i = 1; i <= n; i ++) {
rt[i] = change (rt[i - 1], 1, n, sloc[i - 1] + 1, 1);
}
for (int i = 1; i < n; i ++) {
int l = 0, r = min (n - sloc[i - 1], n - sloc[i]);

while (l < r) {
int mid = (l + r + 1) >> 1;

if (find (sloc[i - 1] + 1, sloc[i - 1] + mid) == find (sloc[i] + 1, sloc[i] + mid)) {
l = mid;
}
else {
r = mid - 1;
}
}
st[i][0] = l;
}
for (int i = 1; i <= Log[n - 1]; i ++) {
for (int j = 1; j < n - (1 << i) + 1; j ++) {
st[j][i] = min (st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
root = new trie;
for (int i = 1; i <= n; i ++) {
trie *p = root;

if (!p->next[c[i] - 'a']) {
p->next[c[i] - 'a'] = new trie;
}
p = p->next[c[i] - 'a'];
for (int j = 2; j <= Q && j <= n - i + 1; j ++) {
if (!p->next[c[i + j - 1] - 'a']) {
p->next[c[i + j - 1] - 'a'] = new trie;
}
p = p->next[c[i + j - 1] - 'a'];
if (p->v.second < i) {
p->v.first ++;
p->v.second = i + j - 2;
}
}
}
for (int i = 1; i <= m; i ++) {
int l, r;

scanf ("%d %d", &l, &r);
if (l == r) {
printf ("-1\n");

continue;
}
if (r - l + 1 > Q) {
int hl = 0, hr = s[l - 1];
int tl = 0, tr = n - s[l - 1] - 1;

while (hl < hr) {
int mid = (hl + hr + 1) >> 1;

if (find_st (s[l - 1] - mid + 1, s[l - 1]) >= r - l + 1) {
hl = mid;
}
else {
hr = mid - 1;
}
}
while (tl < tr) {
int mid = (tl + tr + 1) >> 1;

if (find_st (s[l - 1] + 1, s[l - 1] + mid) >= r - l + 1) {
tl = mid;
}
else {
tr = mid - 1;
}
}

int h = 0;
int sum = 0;

while (h <= n) {
h = ask (rt[s[l - 1] + tr + 1], rt[s[l - 1] - hl], 1, n, h);
if (!(~h)) {
break;
}
h += (r - l);
sum ++;
}
printf ("%d\n", sum);
}
else {
trie *p = root;

for (int j = l; j <= r; j ++) {
p = p->next[c[j] - 'a'];
}
printf ("%d\n", p->v.first);
}
}
}


// ubsan: undefined
// accoders
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define MAXN 100000
#define MAXM 20
#define INF 0x3f3f3f3f

class suffix_array {
private:
template <typename type>
int *first_sort(type *s, type *end) {
pair<type, int> *barrel_sort = new pair<type, int>[end - s];
int *barrel = new int[end - s];

for (type *i = s; i < end; i++) {
barrel_sort[i - s] = make_pair(*i, int(i - s));
}
sort(barrel_sort, barrel_sort + int(end - s));
for (pair<type, int> *i = barrel_sort; i < barrel_sort + int(end - s); i++) {
barrel[i - barrel_sort] = i->second;
}

return barrel;
}
int query_rank(int *loc, int *end) { return loc >= end ? -1 : *loc; }

public:
template <typename type>
int *Sort(type *s, type *end) {
int *barrel = first_sort(s, end);
int *barrel_end = new int[end - s];
int *temporary_barrel = new int[end - s];
int *rank = new int[end - s];
int num = 1;

*(rank + *barrel) = 0;
for (int *i = barrel + 1; i < barrel + int(end - s); i++) {
if (*(s + *i) != *(s + *(i - 1))) {
barrel_end[num - 1] = i - barrel - 1;
num++;
}
*(rank + *i) = num - 1;
}
barrel_end[num - 1] = int(end - s) - 1;
for (int len = 1; len < end - s; len <<= 1) {
for (type *i = s; i < end; i++) {
temporary_barrel[i - s] = barrel[i - s];
}
for (type *i = end - 1; i >= s; i--) {
if (temporary_barrel[i - s] - len >= 0) {
barrel[barrel_end[rank[temporary_barrel[i - s] - len]]--] = temporary_barrel[i - s] - len;
}
}
for (int i = 0; i < len; i++) {
barrel[barrel_end[rank[i + int(end - s) - len]]--] = i + int(end - s) - len;
}
num = 1;
for (int *i = barrel + 1; i < end - s + barrel; i++) {
if (*(rank + *i) != *(rank + *(i - 1)) ||
query_rank(rank + *i + len, rank + int(end - s)) !=
query_rank(rank + *(i - 1) + len, rank + int(end - s))) {
barrel_end[num - 1] = i - barrel - 1;
num++;
}
}
barrel_end[num - 1] = int(end - s) - 1;
for (int t = 0, i = 0; t < num; t++) {
while (i <= barrel_end[t]) {
rank[barrel[i]] = t;
i++;
}
}
}

return rank;
}
} sa;
struct node {
node *sonl = 0, *sonr = 0;
int v = 0;
} * rt[MAXN + 5];

char c[MAXN + 5];
int sloc[MAXN + 5];
int st[MAXN + 5][MAXM + 5];
int Log[MAXN + 5];
unsigned long long b[MAXN + 5], Hash[MAXN + 5];
map<unsigned long long, pair<int, int> > Map;

long long find(int l, int r) {
if (l > r) {
return 0;
}

return Hash[r] - Hash[l - 1] * b[r - l + 1];
}
int find_st(int l, int r) {
if (l > r) {
return INF;
} else {
int u = Log[r - l + 1];

return min(st[l][u], st[r - (1 << u) + 1][u]);
}
}
node *change(node *p, int l, int r, int loc, int v) {
node *new_p = new node;

if (p) {
*new_p = *p;
}
new_p->v += v;
if (l == r) {
return new_p;
}

int mid = (l + r) >> 1;

if (loc <= mid) {
new_p->sonl = change(new_p->sonl, l, mid, loc, v);
} else {
new_p->sonr = change(new_p->sonr, mid + 1, r, loc, v);
}

return new_p;
}

int ask(node *p, int l, int r, int h) {
if (!p || p->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask(p->sonr, mid + 1, r, h);
} else {
int v = ask(p->sonl, l, mid, h);

if (~v) {
return v;
} else {
return ask(p->sonr, mid + 1, r, h);
}
}
}
int ask(node *p1, node *p2, int l, int r, int h) {
if (!p2) {
}
if (!p1 || p1->v - p2->v == 0) {
return -1;
}
if (l == r) {
return l;
}

int mid = (l + r) >> 1;

if (h > mid) {
return ask(p1->sonr, p2->sonr, mid + 1, r, h);
} else {
int v = ask(p1->sonl, p2->sonl, l, mid, h);

if (~v) {
return v;
} else {
return ask(p1->sonr, p2->sonr, mid + 1, r, h);
}
}
}

int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);

int n, m;
int Q;

scanf("%d %d", &n, &m);
Q = sqrt(n);
scanf("%s", c + 1);
b[0] = 1;
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] * 13331;
Hash[i] = Hash[i - 1] * 13331 + c[i];
}
Log[0] = 0;
Log[1] = 0;
for (int i = 2; i <= n; i++) {
Log[i] = Log[i >> 1] + 1;
}

int *s = sa.Sort(c + 1, c + 1 + n);

for (int i = 0; i < n; i++) {
sloc[s[i]] = i;
}
for (int i = 1; i <= n; i++) {
rt[i] = change(rt[i - 1], 1, n, sloc[i - 1] + 1, 1);
}
for (int i = 1; i < n; i++) {
int l = 0, r = min(n - sloc[i - 1], n - sloc[i]);

while (l < r) {
int mid = (l + r + 1) >> 1;

if (find(sloc[i - 1] + 1, sloc[i - 1] + mid) == find(sloc[i] + 1, sloc[i] + mid)) {
l = mid;
} else {
r = mid - 1;
}
}
st[i][0] = l;
}
for (int i = 1; i <= Log[n - 1]; i++) {
for (int j = 1; j < n - (1 << i) + 1; j++) {
st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= Q && j <= n - i + 1; j++) {
unsigned long long v = find(i, i + j - 1);
map<unsigned long long, pair<int, int> >::iterator it = Map.find(v);

if (it == Map.end()) {
Map.insert(make_pair(v, make_pair(1, i + j - 2)));
} else if (it->second.second < i) {
it->second.first++;
it->second.second = i + j - 2;
}
}
}
for (int i = 1; i <= m; i++) {
int l, r;

scanf("%d %d", &l, &r);
if (l == r) {
printf("-1\n");

continue;
}
if (r - l + 1 > Q) {
int hl = 0, hr = s[l - 1];
int tl = 0, tr = n - s[l - 1] - 1;

while (hl < hr) {
int mid = (hl + hr + 1) >> 1;

if (find_st(s[l - 1] - mid + 1, s[l - 1]) >= r - l + 1) {
hl = mid;
} else {
hr = mid - 1;
}
}
while (tl < tr) {
int mid = (tl + tr + 1) >> 1;

if (find_st(s[l - 1] + 1, s[l - 1] + mid) >= r - l + 1) {
tl = mid;
} else {
tr = mid - 1;
}
}

int h = 0;
int sum = 0;

while (h <= n) {
h = ask(rt[s[l - 1] + tr + 1], rt[s[l - 1] - hl], 1, n, h);
if (!(~h)) {
break;
}
h += (r - l);
sum++;
}
printf("%d\n", sum);
} else {
printf("%d\n", Map[find(l, r)].first);
}
}
}