[ABC272F] Two Strings Solution

• [ABC272F] Two Strings Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定两字符串 $ S, T $，求两字符串及其分别循环同构的所有字符串按字典序排序后顺序对个数，定义顺序对为 $ S $ 循环同构的字符串小于等于 $ T $ 循环同构的字符串的对数。

Solution

二分哈希，SA，SAM。

首先经典套路，对于循环同构直接断环然后倍长，以此其长度为 $ n $ 的子串可以表示所有循环同构的串，于是想到对于本题，倍长 $ S, T $，按照 S + S + T + T 的顺序排一下，此时对于其中起始点为 $ [1, n] \cup [2n + 1, 3n] $，长度为 $ n $ 的所有子串进行字典序排序然后求顺序对即可。

上述排序过程显然可以哈希之后，二分判断，复杂度大概是 $ O(n \log^2 n) $，但是这样不够优秀，显然也可以用 SA 求解，但是我不想写 SA，于是我们考虑强行使用 SAM 解决。

这个做法常数较大且细节较多，需要对 SAM 有一定的理解，建议先尝试用 SAM 写一下后缀排序后再考虑这道题。

再次思考一下我们的问题，显然可以转换为对原串的所有定长（即长度为 $ n $）子串之间可重复地排序。

不考虑可重复，不考虑复杂度，一个显而易见的思路就是我们顺序插入建出 SAM，显然在 SAM 中每走一步就会使长度 $ +1 $，且 SAM 可以表示出原串的任意子串，于是我们在 SAM（具体来说就是 SAM 的 DAG）上 dfs，然后贪心地优先走字典序较小的 trans，这样当深度（或者说步数）达到 $ n $ 的时候，我们直接将这个点对应的插入的位置 $ idx $ 存下来，这个存储的顺序就是对应终止于 $ idx $ 长度为 $ n $ 的字符串之间的字典序顺序关系。

现在让我们依次解决这些问题。

首先对于重复的问题，终止节点，或者说就是 $ endpos $ 不同的相同串，我们应该均保留，而上述过程中显然我们对于一个 $ endpos $ 的等价类中只保留了一个，而这个也很好处理，我们只需要对于找到的节点，遍历其在 Parent Tree 上的整个子树保留整棵子树上的所有 $ idx $ 即可。

然后考虑复杂度，一般来讲树上的搜索是可控的，而 DAG 上的搜索则不同，甚至是指数级的，于是我们想到尝试将这个过程从 SAM 上搜索转为从 Parent Tree 上搜索，这一部分的思路与 SAM 求 SA 较为相似，首先思考 SAM 与 Parent Tree 的区别，SAM 中的边是在尾部追加字符，而 Parent Tree 则是在前面插入字符。我们考虑将原串倒序插入 SAM，这样在 Parent Tree 中向更深走的时候意义就会变为追加后缀，而每个等价类中又代表着连续长度的子串，那么当我们在 Parent Tree 搜索时若 $ len \ge n $，则说明当前所在的 $ endpos $ 等价类中子串长度刚好会包括 $ n $，于是再次搜索这个点的子树并保留即可。

接下来不难发现这样是不存在贪心的，也就是说此过程是无序的，而 link 并不像 trans 一样本身带有字符，而对于这里的处理又要考虑到 SAM 中 Parent Tree 的本质，即在 SAM 中进行压缩，换句话说就是对于一个 $ v \rightarrow u $ 的 link，Parent Tree 中 $ u $ 为 $ v $ 的子节点，那么应该满足 $ u $ 追加若干长度后达到 $ v $，而此时我们的贪心就需要考虑到从 $ u $ 到 $ v $ 的过程中的 $ u $ 之后的第一个字符的字典序关系，这个是显然的，且若第一个字符相同那么一定不会被分裂成两个点，所以我们依次为依据，想到 $ u $ 是 $ v $ 的前缀，那么从 $ v $ 的初始位置（注意这里反向插入原串后 $ endpos $ 或者说代码中的 $ idx $ 的意义改为子串初始位置）位移 $ u $ 的长度后以原串中的对应位置的字符为关键字进行偏序地贪心即可。具体来说，Parent Tree 每条边的边权应为 p->idx + p->link->len。

下一个细节，对于建 SAM 时分裂出来的点，从意义上来讲其 $ idx $ 应该为对应次插入时的 $ idx $，且我们在记录答案时对于分裂出的点应该忽略。

再一个细节就是我们在搜索子树的时候不能直接返回一个 basic_string 等容器，否则会因递归多次导致复杂度退化。

而最终统计答案时，我们只需要保留所有范围在 $ [1, n] \cup [2n + 1, 3n] $ 的答案并记录即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define d(c) (c - 'a')

template < typename T = int >
inline T read(void);

struct Edge;
struct Node{
    unordered_map < int, Node* > trans;
    Node* link;
    int len;
    int idx;
    bool flag;
    Edge* head;
    int val;
    OPNEW;
}nd[2100000];
ROPNEW_NODE;
Node* root;

struct Edge{
    Edge* nxt;
    Node* to;
    int val;
    OPNEW;
}ed[4100000];
ROPNEW;

int N;
string S, T;
string base;
basic_string < bool > sorted;
basic_string < int > ret;

void Insert(int c, int idx){
    static Node* lst = root;
    Node* p = lst; Node* cp = lst = new Node; cp->idx = idx; cp->flag = true;
    cp->len = p->len + 1;
    while(p && !p->trans[c])p->trans[c] = cp, p = p->link;
    if(!p)cp->link = root;
    else if(p->trans[c]->len == p->len + 1)cp->link = p->trans[c];
    else{
        auto q = p->trans[c], sq = new Node(*q); sq->idx = idx; sq->flag = false;
        sq->len = p->len + 1;
        cp->link = q->link = sq;
        while(p && p->trans[c] == q)p->trans[c] = sq, p = p->link;
    }
}
void Link(void){
    auto endp = new Node();
    for(auto p = nd; p != endp;++p)
        if(p->link)
            p->link->head = new Edge{p->link->head, p, base.at(p->idx + p->link->len)};
}
void dfs_subt(Node* p){
    if(p->flag && ((1 <= p->idx && p->idx <= N) || (N * 2 + 1 <= p->idx && p->idx <= N * 3)))ret += p->idx;
    for(auto i = p->head; i; i = i->nxt)dfs_subt(SON);
}
void dfs(Node* p = root){
    if(N <= p->len){
        ret.clear();
        dfs_subt(p);
        int cnt1(0);
        for(auto pos : ret)
            if(N * 2 + 1 <= pos && pos <= N * 3)++cnt1;
            else if(1 <= pos && pos <= N)sorted += false;
        while(cnt1--)sorted += true;
        return;
    }
    basic_string < Edge* > sons;
    for(auto i = p->head; i; i = i->nxt)sons += i;
    sort(sons.begin(), sons.end(), [](Edge* a, Edge* b)->bool{return a->val < b->val;});
    for(auto son : sons)dfs(son->to);
}

int main(){
    // freopen("in.txt", "r", stdin);
    root = new Node(); root->idx = -1; root->len = 0;
    N = read();
    cin >> S >> T;
    base = '#' + S + S + T + T;
    for(int i = N * 4; i >= 1; --i)Insert(d(base.at(i)), i);
    Link(), dfs();
    ll ans(0), sumS(0);
    for(auto v : sorted)if(v)ans += sumS; else ++sumS;
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int idx(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')idx = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= idx;
    return ret;
}

UPD

update-2023_02_15 初稿