[Luogu] U18590 采集矿石

https://www.luogu.org/problemnew/show/U18590

后缀数组？？？

不会

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>

using namespace std;
const int N = 1e3 + 10;

#define yxy getchar()
#define R freopen("gg.in", "r", stdin)

char s[N];
int sum[N], len, js, Answer;
struct Node{
    string s;
    int l, r, w, num;
}A[N * N];
struct Node_2{
    int l, r;
}Ans[N * N];
map <string, bool> mp; 

inline int read(){
    int x = 0; char c = yxy;
    while(c < '0' || c > '9') c = yxy;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = yxy;
    return x;
}

bool cmp(Node a, Node b) {return a.s > b.s;}
bool cmp2(Node_2 a, Node_2 b) {return a.l < b.l;}

string get_string(int l, int r){
    string ret;
    for(int i = l; i <= r; i ++) ret += s[i];
    return ret;
}

int main()
{
    scanf("%s", s + 1);
    len = strlen(s + 1);
    for(int i = 1; i <= len; i ++) sum[i] = read(), sum[i] += sum[i - 1];
    for(int i = 1; i <= len; i ++){
        for(int j = i; j <= len; j ++){
            string ss = get_string(i, j);
            A[++ js].s = ss;
            A[js].l = i; A[js].r = j; A[js].w = sum[j] - sum[i - 1];
        }
    }
    sort(A + 1, A + js + 1, cmp);
    int px(1);
    A[1].num = 1;
    for(int i = 2; i <= js; i ++)
        if(A[i].s != A[i - 1].s) A[i].num = ++ px;
        else A[i].num = px;
    for(int i = 1; i <= js; i ++)
        if(A[i].num == A[i].w) {
            Ans[++ Answer].l = A[i].l;
            Ans[Answer].r = A[i].r;
        }
    sort(Ans + 1, Ans + Answer + 1, cmp2);
    printf("%d
", Answer);
    for(int i = 1; i <= Answer; i ++) printf("%d %d
", Ans[i].l, Ans[i].r);
    return 0;
}
/*
aaaa
1 1 1 1
*/