【luoguP4600】[HEOI2012]旅行问题

这个题……tm是个语文阅读题吧。

翻译成人话就是,现在给定两个串,取他们的前缀,设这两个前缀分别为a,b,要求出一个最长的后缀,且这个后缀一定作为过某个字符串的前缀出现过。

仔细思考下……这tm不是建一个ac自动机然后fail树求lca吗

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;  
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = - x;
}

const int ms = (1 << 20), mo = 1e9 + 7;

int n, m, la, lb, lc, ld, pos[ms << 1], len[ms], ta, Q[ms];

char s[ms];

struct Acam
{
    int ch[ms][26], ne[ms], de[ms], tot, cnt, head[ms], ha[ms], tp[ms], sz[ms], son[ms], fa[ms];

    inline void insert(int l)
    {
        int no = 0;
        for(ri i = 0; i < l; i ++)
        {
            if(!ch[no][s[i] - 'a'])
                ch[no][s[i] - 'a'] = ++ cnt, ha[ch[no][s[i] - 'a']] = (26ll * ha[no] + s[i] - 'a') % mo;
            no = ch[no][s[i] - 'a'], pos[++ ta] = no;
        }
    }

    inline void init()
    {
        re(n); int Len;
        for(ri i = 1; i <= n; i ++)
            scanf("%s", s), Len = strlen(s), len[i] = len[i - 1] + Len, insert(Len);
    }

    struct in
    {
        int to, ne;
    }ter[ms << 1];

    inline void Build(int f, int l)
    {
        ter[++ tot] = (in){l, head[f]}, head[f] = tot;
        ter[++ tot] = (in){f, head[l]}, head[l] = tot;
    }

    void dfs1(int no)
    {
        de[no] = (no != 0) ? de[fa[no]] + 1 : 1, sz[no] = 1;
        for(ri i = head[no]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(to == fa[no])
                continue;
            fa[to] = no, dfs1(to), sz[no] += sz[to];
            if((!son[no]) || (sz[son[no]] < sz[to]))
                son[no] = to;
        }
    }

    void dfs2(int no, int t)
    {
        tp[no] = t;
        if(son[no])
            dfs2(son[no], t);
        for(ri i = head[no]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(to == fa[no] || to == son[no])
                continue;
            dfs2(to, to);
        }
    }

    inline int lca(int x, int y)
    {
        while(tp[x] ^ tp[y])
            de[tp[x]] >= de[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];
        return de[x] <= de[y] ? x : y;  
    }

    inline void build()
    {
        memset(head, -1, sizeof(int) * (cnt + 1)), tot = -1;
        int h1 = 0, t1 = -1;
        for(ri i = 0; i < 26; i ++)
            if(ch[0][i])
                Q[++ t1] = ch[0][i];
        while(h1 <= t1)
        {
            int qaq = Q[h1 ++]; Build(qaq, ne[qaq]);
            for(ri i = 0; i < 26; i ++)
            {
                if(ch[qaq][i])
                    ne[ch[qaq][i]] = ch[ne[qaq]][i], Q[++ t1] = ch[qaq][i];
                else
                    ch[qaq][i] = ch[ne[qaq]][i];
            }
        }
        fa[0] = -1, dfs1(0), dfs2(0, 0);
    }
}acam;

int main()
{
    acam.init(), acam.build();
    re(m);
    while(m --)
    {
        re(la), re(lb), re(lc), re(ld);
        int p1 = pos[len[la - 1] + lb], p2 = pos[len[lc - 1] + ld];
        //cout << p1 << ' ' << p2 << ' ' << acam.lca(p1, p2) << '\n';
        printf("%d\n", acam.ha[acam.lca(p1, p2)]);
    }
}

【luoguP4112】[HEOI2015]最短不公共子串

一个序列自动机+后缀自动机的模板好题
首先第一问和第二问就是送分的,枚举a串的起点,将后缀完全插入进两个自动机,看是否能走到一个空节点就行了。
第三问和第四问是一样的,我们设dp_{i,j}表示目前考虑了a串的前i个字符,走到了自动机j号节点的最短子序列长度即可。
然后方程就是
dp_{i,j}=min(dp_{i-1,j},dp_{i-1,from}+1)这样的东西
然后直接在两个自动机上做dp就可以了。可是我傻子不会第三四问

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 4020;

char a[ms], b[ms];

int n, m, dp[2020][ms];

struct Sam
{
    int ch[ms][26], len[ms], fa[ms], las, cnt;

    inline void insert(int c)
    {
        int p = ++ cnt; len[p] = len[las + 1];
        while(las && (!ch[las][c]))
            ch[las][c] = p, las = fa[las];
        if(!las)
            fa[p] = 1;
        else
        {
            int x = ch[las][c];
            if(len[x] == len[las] + 1)
                fa[p] = x;
            else
            {
                int q = ++ cnt; memcpy(ch[q], ch[x], sizeof(ch[x]));
                len[q] = len[las] + 1, fa[q] = fa[x], fa[x] = fa[p] = q;
                while(las && ch[las][c] == x)
                    ch[las][c] = q, las = fa[las];
            }
        }
        las = p;
    }
}sam;

struct Lam
{
    int cnt, ch[ms][26], las[26];

    inline void insert(int c)
    {
        int no = ++ cnt;
        for(ri i = 0; i < 26; i ++)
            ch[no][i] = las[i];
        las[c] = no;
    }

    inline void init()
    {
        for(ri i = 0; i < 26; i ++)
            ch[1][i] = las[i];
    }
}lam;

inline void ask1()
{
    int pri = 1e9 + 7;
    for(ri i = 1, j; i <= n; i ++)
    {
        int no = 1, ci = 0;
        for(j = i; j <= n; j ++)
        {
            ci ++;
            if(!sam.ch[no][a[j] - 'a'])
                break;
            no = sam.ch[no][a[j] - 'a'];
        }
        if(j <= n)
            pri = min(pri, ci);
    }
    if(pri == 1e9 + 7)
        puts("-1");
    else
        printf("%d\n", pri);
}

inline void ask2()
{
    int pri = 1e9 + 7;
    for(ri i = 1, j; i <= n; i ++)
    {
        int no = 1, ci = 0;
        for(j = i; j <= n; j ++)
        {
            ci ++;
            if(!lam.ch[no][a[j] - 'a'])
                break;
            no = lam.ch[no][a[j] - 'a'];
        }
        if(j <= n)
            pri = min(pri, ci);
    }
    if(pri == 1e9 + 7)
        puts("-1");
    else
        printf("%d\n", pri);
}

inline void ask3()
{
    memset(dp, 63, sizeof(dp));
    dp[0][1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        for(ri j = 1; j <= sam.cnt; j ++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        for(ri j = 1; j <= sam.cnt; j ++)
        {
            int to = sam.ch[j][a[i] - 'a'];
            dp[i][to] = min(dp[i][to], min(dp[i - 1][to], dp[i - 1][j] + 1));
        }
    }
    if(dp[n][0] == dp[n + 1][0])
        puts("-1");
    else
        printf("%d\n", dp[n][0]);
}

inline void ask4()
{
    memset(dp, 63, sizeof(dp));
    dp[0][1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        for(ri j = 1; j <= lam.cnt; j ++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        for(ri j = 1; j <= lam.cnt; j ++)
        {
            int to = lam.ch[j][a[i] - 'a'];
            dp[i][to] = min(dp[i][to], min(dp[i - 1][to], dp[i - 1][j] + 1));
        }
    }
    if(dp[n][0] == dp[n + 1][0])
        puts("-1");
    else
        printf("%d\n", dp[n][0]);
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1), m = strlen(b + 1);
    sam.las = 1, sam.cnt = 1, lam.cnt = 1;
    for(ri i = 1; i <= m; i ++)
        sam.insert(b[i] - 'a');
    for(ri i = m; i; i --)
        lam.insert(b[i] - 'a');
    lam.init();
    ask1(), ask2(), ask3(), ask4();
    system("pause");
}

【luoguP4287】[SHOI2011]双倍回文

这是一个PAM的模板题
考虑一个子串成为双倍回文的条件,长度一定为4的倍数,并且沿着fail指针跳一定能跳到一个长度为其二分之一的子串。
那么就建出一个PAM就行,注意有两个根,一个是长度为偶数的回文串,一个是奇数的,找fail指针的时候,之所以是p-len-1,是因为你要考虑从原来p-1出发,往前跳len格正好到对应位置。建法挺像ACAM的。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 5e5 + 10;

char s[ms];

int n, ans;

struct Pam
{
    int ne[ms], f[ms], len[ms], ch[ms][26], tot, las;

    inline int askfail(int x, int p)
    {
        while(s[p] != s[p - len[x] - 1])
            x = ne[x];
        return x;
    }

    inline void insert(int c, int p)
    {
        int no, Fa = askfail(las, p);
        if(!ch[Fa][c])
        {
            ne[no = ++ tot] = ch[askfail(ne[Fa], p)][c];
            len[no] = len[Fa] + 2, ch[Fa][c] = no;
            if(len[ne[no]] <= (len[no] >> 1))
                f[no] = ne[no];
            else
            {
                int P = f[Fa];
                while((len[P] + 2) > (len[no] >> 1) || s[p] != s[p - len[P] - 1])
                    P = ne[P];
                f[no] = ch[P][c];
            }
        }
        las = ch[Fa][c];
    }

    inline void build()
    {
        len[ne[0] = ++ tot] = -1;
        for(ri i = 1; i <= n; i ++)
            insert(s[i] - 'a', i);
    }

    inline void ask()
    {
        for(ri i = 1; i <= tot; i ++)
            if((!(len[i] & 3)) && len[f[i]] == (len[i] >> 1))
                ans = max(ans, len[i]);
    }
}pam;

int main()
{
    re(n), scanf("%s", s + 1);
    pam.build(), pam.ask();
    printf("%d", ans);
    system("pause");
}

【luoguP4094】[HEOI2016/TJOI2016]字符串

学艺不精学艺不精,sa&sam都是一瓶子不满半瓶子咣当,自闭了。
现在我们要求公共前缀,对sam来说,前缀不好求但后缀好求,翻转整个串,这样就变成公共后缀了,并且这个后缀满足,对于s[b-len+1,a],存在一个结束点和s[d,c]在同一个endpos集合里面并且长度长度至少为len。那么就倒序建一个sam,然后模拟建出后缀树(常见套路),并用线段树合并来维护endpos。
询问的时候二分答案,并且从c所在位置沿着后缀树往上面跳,跳到长度不小于二分值的最上方。然后线段树查询即可。
看不透sa的解法,突然发现自己不懂为什么height维护的是sa_i却可以做原串的lcp,自闭。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef unsigned int uint;

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 1e5 + 10; 

int n, m, tmpsz[ms << 1], poi[ms << 1], pos[ms];

char s[ms];

struct Sam
{
    int ch[ms << 1][26], len[ms << 1], cnt, las, Root[ms << 1], fa[ms << 1][21];

    struct Seg
    {
        int ch[ms << 6][2], su[ms << 6], tot;

        void insert(int &w, int l, int r, int ll)
        {
            if(!w)
                w = ++ tot;
            if(l == r)
            {
                su[w] ++; return;
            }
            int mid = (l + r) >> 1;
            if(ll <= mid)
                insert(ch[w][0], l, mid, ll);
            else
                insert(ch[w][1], mid + 1, r, ll);
            su[w] = su[ch[w][0]] + su[ch[w][1]];
        }

        int merge(int x, int y, int l, int r)
        {
            if((!x) || (!y))
                return x + y;
            if(l == r)
            {
                su[x] += su[y]; return x;
            }
            int mid = (l + r) >> 1, rt = ++ tot;
            ch[rt][0] = merge(ch[x][0], ch[y][0], l, mid), ch[rt][1] = merge(ch[x][1], ch[y][1], mid + 1, r);
            su[rt] = su[ch[rt][0]] + su[ch[rt][1]];
            return rt;
        }

        int ask(int w, int l, int r, int ll, int rr)
        {
            if(!w)
                return 0;
            if(l == ll && r == rr)
                return su[w];
            int mid = (l + r) >> 1;
            if(rr <= mid)
                return ask(ch[w][0], l, mid, ll, rr);
            else if(ll > mid)
                return ask(ch[w][1], mid + 1, r, ll, rr);
            return ask(ch[w][0], l, mid, ll, mid) + ask(ch[w][1], mid + 1, r, mid + 1, rr);
        }
    }seg;

    inline void insert(int c)
    {
        int p = ++ cnt; len[p] = len[las] + 1;
        while(las && (!ch[las][c]))
            ch[las][c] = p, las = fa[las][0];
        if(!las)
            fa[p][0] = 1;
        else
        {
            int x = ch[las][c];
            if(len[x] == len[las] + 1)
                fa[p][0] = x;
            else
            {
                int q = ++ cnt; len[q] = len[las] + 1, fa[q][0] = fa[x][0];
                memcpy(ch[q], ch[x], sizeof(ch[q])), fa[x][0] = q, fa[p][0] = q;
                while(las && ch[las][c] == x)
                    ch[las][c] = q, las = fa[las][0];
            }
        }
        las = p;
    }

    inline void build()
    {
        cnt = 1, las = 1;
        reverse(s + 1, s + 1 + n);
        for(ri i = 1; i <= n; i ++)
            insert(s[i] - 'a'), seg.insert(Root[las], 1, n, i), pos[i] = las;
        for(ri i = 1; i <= cnt; i ++)
            tmpsz[len[i]] ++;
        for(ri i = 1; i <= n; i ++)
            tmpsz[i] += tmpsz[i - 1];
        for(ri i = 1; i <= cnt; i ++)
            poi[tmpsz[len[i]] --] = i;
        for(ri i = 1; i <= 20; i ++)
            for(ri j = 1; j <= cnt; j ++)
                fa[j][i] = fa[fa[j][i - 1]][i - 1];
        for(ri i = cnt; i; i --)
            if(fa[poi[i]][0])
                Root[fa[poi[i]][0]] = seg.merge(Root[fa[poi[i]][0]], Root[poi[i]], 1, n);
    }

    inline bool check(int Len, int p, int l, int r)
    {
        for(ri i = 20; ~i; i --)
            if(len[fa[p][i]] >= Len && fa[p][i])
                p = fa[p][i];
        //cout << p << '\n';
        return seg.ask(Root[p], 1, n, l + Len - 1, r);
    }

    inline void solve()
    {
        int a, b, c, d;
        while(m --)
        {
            re(a), re(b), re(c), re(d);
            a = n + 1 - a, b = n + 1 - b, c = n + 1 - c, d = n + 1 - d;
            int l = 0, r = min(a - b + 1, c - d + 1), ans = 0;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(check(mid, pos[c], b, a))
                    ans = mid, l = mid + 1;
                else
                    r = mid - 1;
            }   
            printf("%d\n", ans);
        }
    }
}sam;

int main()
{
    re(n), re(m);
    scanf("%s", s + 1);
    sam.build(), sam.solve();
}

【算法】后缀数组

其实后缀数组是个数据结构啊……但是我习惯学个新东西叫算法了
其实也不是最近才学的,之前3月学过一次,但是印象并不是完全深刻,这次再复习一遍
先安利https://blog.csdn.net/YxuanwKeith/article/details/50636898 五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码),这篇博客讲的挺好的,特别是height数组的证明
这篇http://www.cnblogs.com/zwfymqz/p/8413523.html 也是不错的,图画的挺明白的,不过代码讲的并不是特别详细
后缀数组是个非常有趣又有用的东西,有两种构建办法,O(nlogn)的倍增法和O(n)的DC3法,但是最常用的还是倍增,因为好写啊。所以这里讲的也是倍增法
我们先从一个个单个字母考虑,这个时候显然他们字典序是第一关键字,在原序列位置是第二关键字,那么我们排个序,就可以得到现在的一个相对排名,这个排名的大小也就是这个字符串字典集的大小
然后我们现在将每个字母后面的关键字和它本身的关键字按照前为第一关键字,后为第二关键字,将它们拼起来,这个时候我们发现我们得到了长度为2的字串的相对顺序

也就是这张图画的了
那么我们既然可以从长度为1的关系推出长度为2的关系,当然也可以从长度为2的推出长度为4的……一直推到我们成功的将所有后缀区分成功停止。最坏的时间复杂度是nlogn的
接下来是整个过程

这是一个大体的算法流程,具体实现呢?
先设几个数组
rak[i]表示原字符串以第i位开头的后缀的排名,sa[i]表示当前排名为i的后缀起点在哪,tp[i]表示第二关键字排第i的它所在后缀起点在哪
那么显然rak[sa[i]] = i, sa[rak[i]] = i
这样我们就可以互相转化了
那么我们就可以先处理出之前的sa数组和之前的tp数组,然后将这两个分别作为第一关键字和第二关键字,去跑个排序,就可以得出新的sa数组,再通过sa得到rak数组
现在我们用快排什么的复杂度都是nlogn,这样太慢了,因为我们有更快的排序——基数排序
基数排序思想和桶排有点相像,但是它要比桶排高明,因为它复杂度是几乎可以达到O(n)的,而且它空间也远远小于桶排
还记得刚才我们说通过两个关键字得到新的顺序吗,基数排序和这个类似,我们每次将一个数截成好几部分,然后我们开个桶,桶的大小称为基数,然后我们用桶排的思想,按照当前比较关键字的大小放到相应的桶,我们就可以得知该关键字某个值有多少个,我们再求一边前缀和,再倒序塞回去,我们默认并保证之前的关键字从小到大排序,这样就得到了几个连续的块,这些块内按照当前考虑的所有关键字严格有序,我们从低位到高位排,因为低位已经保证有序了,对于每次高位更新,都是先插入低位值较大的,而本身目前最高位关键字也是有序的,保证每个最高位关键字都有个属于自己的块,所以目前被考虑的所有关键字才严格有序。这样就能保证排序的正确性了。代码会和构建后缀数组的其他步骤放在一起
那么每次我们倍增的过程相当于新增关键字,先处理好tp数组,有些长度较短的后缀没有第二关键字,我们就认为它们第二关键字是0,剩下的我们按照上一轮的sa[i]来处理,假设我们现在考虑的是长度为w的字串,我们要用它们转移到w << 1的字串,显然tp[i]就等于sa[i] – w,因为sa[i]是当所有子串长度不超过w的时候排名为i的字串,那么w << 1之后,他就会作为sa[i] – w这个位置上的第二关键字,所以tp[i]的起点为sa[i] – w
然后我们再去跑基数排序,求每个位置上的后缀目前的排名,并同时求出字典集大小,直到字典集大小和原字符串长度一样长
luogu P3809【模板】后缀排序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

const int ms = 1000010;

int m = 127, len, s[ms], rak[ms], sa[ms], tp[ms], sz[ms];

inline void re()
{
    char a = getchar();
    while((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || (a >= '0' && a <= '9'))
        s[++ len] = a - 48, a = gch();
}

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        sz[i] = 0;
    for(ri i = 1; i <= len; i ++)
        sz[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        sz[i] += sz[i - 1];
    for(ri i = len; i >= 1; i --)
        sa[sz[rak[tp[i]]] --] = tp[i];/*tp[i]表示第二关键字排i的位置在tp[i]
        rak[tp[i]]就是单纯只按第二关键字排名为i的后缀开头位置 
        这个位置按照第一关键字排序,排名第几
        这样做我们首先保证tp是从大往小走的
        然后又因为基数排序的性质我们把前面的第一关键字按照数值大小丢进新的序列中
        所以这就保证了正确性*/ 
}

int main()
{
    re();
    for(ri i = 1; i <= len; i ++)
        rak[i] = s[i], tp[i] = i;
    rsort(); 
    for(ri w = 1, p = 1; p < len; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = len - w + i;//因为后面这些后缀没有第二关键字,自然按第二关键字排名小
        for(ri i = 1; i <= len; i ++)
            if(sa[i] > w)//如果这个后缀往前走w步,这个位置上的后缀有第二关键字的话 
                tp[++ p] = sa[i] - w;/*因为对于排好序的sa数组,在我们要求w << 1后缀时候
                sa[i]的前w个字符是sa[i - w]接下来的后w个字符,因此我们- w*/
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= len; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
        //比较排名相邻两个串,如果俩关键字相同没必要管,否则++p 
    }
    for(ri i = 1; i <= len; i ++)
        printf("%d ", sa[i]);
}

但是求sa和rak并不是后缀数组最为重要的功能,它真正的用处在与求height数组
我们定义height[i] = lcp(sa[i], sa[i – 1]),h[i] = height[rak[i]], h[i] >= h[i – 1] – 1
这个是为啥呢?
h[i]表示的是以i的开头的后缀和它前一名的后缀的公共前缀,那么我们设sa[k]是sa[i – 1]前一名的后缀,那么显然h[i – 1]是这两者的公共前缀,我们现在都向前一位,变成了sa[k + 1]和sa[i],那么它们就相当于同时砍掉开头的一个字符,它们的公共前缀也就是h[i – 1] – 1,那么对于刚才那个不等式,如果h[i – 1]为0或者1的时候显然成立,否则我们继续假设与i最匹配的后缀为x,那么lcp(sa[k + 1], sa[i]) = h[i – 1] – 1,如果x比k + 1一样或者还要匹配的话,那么h[i] >= h[i – 1] – 1
所以我们可以两句话求出这个height
for(ri i = 1; i <= n; h[rak[i ++]] = k)
for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);

这两句话非常直接,k就是之前的h[i]这个值,我们每次从上次结束的位置继续开始,不停往下找,直到不公共为止
例题
poj 1743 Musical Theme
这个题目是求两个不相重叠的相同字串的最长长度,当然你要先把这个序列差分下,求差分值相同的。我们可以用二分+后缀数组解决这个题,这个题就是利用的height数组的性质,假如height数组有一个连续大于x的区间,那么至少可以保证这个区间所包含的所有后缀有个共同的长度为x的后缀,因为lcp(i, j, k) = min(lcp(i, j), lcp(j, k))
那么这个时候二分答案就很明显了,我们可以二分答案,然后在height数组上找一个长度大于mid值并且的所有数都大于等于mid的这么一个区间,之所以长度要大于mid,是因为我们中间需要留个空不让这两个子串连在一起

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin));
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 20020;

int n, m, l, r, b[ms], s[ms], sa[ms], rak[ms], tp[ms], num[260], h[ms];

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        num[i] = 0;
    for(ri i = 1; i <= n; i ++)
        num[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        num[i] += num[i - 1];
    for(ri i = n; i >= 1; i --)
        sa[num[rak[tp[i]]] --] = tp[i];
}

inline void asksa()
{
    rsort();
    for(ri w = 1, p = 0; p < n; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = n - w + i;
        for(ri i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
    }
    ri k = 0, j;
    for(ri i = 1; i <= n; h[rak[i ++]] = k)
        for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);
}

inline bool check(int x)
{
    int mx = - 1e9 - 7, mi = 1e9 + 7;
    for(ri i = 3; i <= n; i ++)
    {
        if(h[i] >= x)
        {
            mi = min(mi, min(sa[i], sa[i - 1])), mx = max(mx, max(sa[i], sa[i - 1]));
            if(mx - mi > x)
                return 1;
        }
        else
            mx = - 1e9 - 7, mi = 1e9 + 7;
    }
    return 0;
}

int main()
{
    re(n);
    while(n > 0)
    {
        m = 233;
        for(ri i = 1; i <= n; i ++)
            re(b[i]); 
        for(ri i = 1; i < n; i ++)
            s[i] = b[i + 1] - b[i] + 88;
        s[n] = 0;
        for(ri i = 1; i <= n; i ++)
            rak[i] = s[i], tp[i] = i;
        asksa(); l = 0, r = (n - 1) >> 1;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", (l >= 4) ? l + 1: 0); re(n);
    }
    return 0;
}

luogu P2852 [USACO06DEC]牛奶模式Milk Patterns
这个题目和刚才大同小异,只不过现在从不可重叠变成了可以重叠,从2个变成了k个,那么我们稍微改改,还是二分一个mid值,然后只要有个长度连续大于k的区间就行
我就改了改check函数和预处理

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin));
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 20020;

int n, m, k, l, r, b[ms], s[ms], sa[ms], rak[ms], tp[ms], num[20060], h[ms];

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        num[i] = 0;
    for(ri i = 1; i <= n; i ++)
        num[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        num[i] += num[i - 1];
    for(ri i = n; i >= 1; i --)
        sa[num[rak[tp[i]]] --] = tp[i];
}

inline void asksa()
{
    rsort();
    for(ri w = 1, p = 0; p < n; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = n - w + i;
        for(ri i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
    }
    ri k = 0, j;
    for(ri i = 1; i <= n; h[rak[i ++]] = k)
        for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);
}

inline bool check(int x)
{
    int mx = 1, mi = 1;
    for(ri i = 2; i <= n; i ++)
    {
        if(h[i] >= x)
            mx ++;
        else
            mi = mx = i; 
        if(mx - mi + 1 >= k)
            return 1;
    }
    return 0;
}

int main()
{
    re(n);
    m = 20000, re(k);
    for(ri i = 1; i <= n; i ++)
        re(s[i]); 
    for(ri i = 1; i <= n; i ++)
        rak[i] = s[i], tp[i] = i;
    asksa(); l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}

继续添加,如何做字典序第k小的子串,可重/不可重?
这就要利用h数组性质了,我们先算不可重的,不可重的话你考虑h数组是存的lcp,也就是重复的一部分,那么一个后缀去掉lcp的部分长度,就是他能贡献的子串个数,那么因为是拍好序了的,所以对于去重的部分其实字典序已经拍好了,因此我们可以处理出所有后缀的贡献,算个前缀和,二分就可以了。
那么可重呢,这个时候我们分析假如有后缀aab和ab,ab会产生一个a子串,字典序要比ab靠前,这时候我们考虑怎样对前面的产生影响……实际上也就是一个lcp的影响范围……如果中间是0会隔断,所以建个单调栈维护然后瞎鸡儿预处理就好了。