2019/8/16 day13 解题日志

2019-08-16

字数统计: 1.7k字 | 阅读时长: 8分

day13

前言

自从6月停止day cnt++系列，准备ecnu夏令营后，到今天已经有整整两个月没有自主做过有意思的题（多校训练遇到的题目可能还远远不够，既然目标放在了gold medal，就应该为此付出相应的努力）。直到hdu多校还剩两场，发现队伍卡在rank 120上不去，另外求职路上也遇到一些挫折，想着需要重新开始每日一题了。
可能会更频繁的更新这个系列，总之，provincial and regional加油。

题意

给$n$个字符串$s_{i}$，设$s_{i} + s_{j}$表示两个字符串简单拼接，设$f(first,second)$表示second在first中作为子串出现的次数。
给一个字符串$t$，问：
$\sum_{i=1}^{n} \sum_{j=1}^{n} f(t,s_{i} + s_{j})$

数据范围：$1\le n \le 200000,\sum_{i=1}^{n}|s| \le 200000,|s|\le |t| \le 200000 $

思路

这是一道很明显的字符串题了，一定需要考虑到字符串匹配算法。
考虑$KR-hash$，依次维护出$pre[i]$表示以下标i的字符为结束的$s_i$数量，和$suf[i]$ 表示以下标i字符为起点的$s_i$数量。
做是可以做出来，但是需要对n个s串都做一次遍历t串的循环，未免有点夸张。
考虑优化，kmp算法似乎也帮不上忙。
多串匹配问题，考虑ac自动机：

0.在DFA中，从root出发到达每个状态的路径，都是某个字符串的前缀（这是trie树的内容）。
1.而ac自动机考虑到匹配过程中的失配问题，就要找到对于当前状态cur的失配位置fail，使得S(cur)在trie树中能找到的最长后缀是S(fail)。
2.fail指针的建立可以动态的由father状态转移得到，看看我们现在要考虑什么问题呢？
3.如何快速得到pre[]和suf[]数组的值，由于这里pre[]和suf[]的性质同类，不妨只讨论pre[]。

4.pre[i]本质上就是，有多少个s以t[i]结尾。

5.以n个s建立trie树，并且构造fail指针，当t的某个前缀走到了状态cur的时候，根据fail的性质，可以知道，从cur开始的fail递归链里面，有多少个endpoint，就有多少个s以t[i]结尾。
6.那么问题岂不是变成，在转移一个t[i]之后，fail递归链里面，有多少个endpoint？

7.暴力回跳看起来很蠢。比如s是如下形式：

4
a
aa
aaa
aaaaaaaa...aaaaaa
aaaaaaaa...aaaaaaaaaaaa（这是t串）

这种回跳的复杂度爆炸，原因是大量重复的fail指针都是在某个s串的某一后缀慢慢挪动，而真正对答案有贡献的串寥寥无几。
考虑常见优化：设ffail[cur]指向fail指针里，作为某个串endpoint的状态，有如下转移：

1	ffail[cur] = endpoint[fail[cur]]?fail[cur]:ffail[fail[cur]];

8.那么到此为止这个题目就差不多完成了。还能优化吗？
9.由于fail指针指向的位置是确定的，fail指针其实构成了一棵树，采用动态规划的方法可以省去回跳的步骤，直接O(1)维护便可。

//动态规划的思路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
 
int cnt2[maxn];
int cnt[maxn];
 
struct trie{
    int nxt[maxn][26],fail[maxn],g[maxn];
    int ed[maxn];
    int rt,L;
    int newnode(){
        memset(nxt[L],-1,sizeof nxt[L]);
        ed[L++]=0;
        return L-1;
    }
    void init(){
        L=0;rt=newnode();
    }
    void insert(const string& buf){
        int len=buf.size();
        int now=rt;
        for(int i=0;i<len;++i){
            if(nxt[now][buf[i]-'a']==-1)nxt[now][buf[i]-'a']=newnode();
            now=nxt[now][buf[i]-'a'];
        }ed[now]++;
    }
    void build(){
        queue<int>q;
        fail[rt]=rt;  g[rt]=rt;
        for(int i=0;i<26;++i){
            if(nxt[rt][i]==-1)nxt[rt][i]=rt;
            else {
                fail[nxt[rt][i]]=rt;  g[nxt[rt][i]]=rt;
                q.push(nxt[rt][i]);
            }
        }
        while(!q.empty()){
            int now = q.front();q.pop();
            for(int i=0;i<26;++i){
                if(nxt[now][i]==-1)nxt[now][i]=nxt[fail[now]][i];
                else{
                    fail[nxt[now][i]]=nxt[fail[now]][i];
                    ed[nxt[now][i]] += ed[fail[nxt[now][i]]];
                    q.push(nxt[now][i]);
                }
            }
        }
    }
    void query(const string& buf){
        int len=buf.size();
        int now = rt;
        for(int i=0;i<len;++i){
            now = nxt[now][buf[i]-'a'];
            cnt[i]+=ed[now];
        }
    }
}a,b;
 
string t;
string s[maxn];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;int n;cin>>n;
    a.init();
    for(int i=1;i<=n;++i){
        cin>>s[i];
        a.insert(s[i]);
    }
    a.build();
    a.query(t);
    memcpy(cnt2,cnt,sizeof cnt);
    memset(cnt,0,sizeof cnt);
    a.init();
    for(int i=1;i<=n;++i){
        reverse(s[i].begin(),s[i].end());
        a.insert(s[i]);
    }
    a.build();
    reverse(t.begin(),t.end());
    a.query(t);
    ll ans=0;
    for(int i=0;i<t.size()-1;++i){
        ans += 1ll*cnt2[i]*cnt[t.size()-i-2];
    }
    cout<<ans;
    return 0;
}

相对而言，优化fail指针的方法可能使用场景更广泛：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
 
int cnt2[maxn];
int cnt[maxn];
 
struct trie{
    int nxt[maxn][26],fail[maxn],g[maxn];
    int ed[maxn];
    int rt,L;
    int newnode(){
        memset(nxt[L],-1,sizeof nxt[L]);
        ed[L++]=0;
        return L-1;
    }
    void init(){
        L=0;rt=newnode();
    }
    void insert(const string& buf){
        int len=buf.size();
        int now=rt;
        for(int i=0;i<len;++i){
            if(nxt[now][buf[i]-'a']==-1)nxt[now][buf[i]-'a']=newnode();
            now=nxt[now][buf[i]-'a'];
        }ed[now]++;
    }
    void build(){
        queue<int>q;
        fail[rt]=rt;  g[rt]=rt;
        for(int i=0;i<26;++i){
            if(nxt[rt][i]==-1)nxt[rt][i]=rt;
            else {
                fail[nxt[rt][i]]=rt;  g[nxt[rt][i]]=rt;
                q.push(nxt[rt][i]);
            }
        }
        while(!q.empty()){
            int now = q.front();q.pop();
            for(int i=0;i<26;++i){
                if(nxt[now][i]==-1)nxt[now][i]=nxt[fail[now]][i];
                else{
                    fail[nxt[now][i]]=nxt[fail[now]][i];
                    if(ed[ fail[nxt[now][i]] ]){
                        g[nxt[now][i]] = fail[nxt[now][i]];
                    } else g[nxt[now][i]] = g[fail[nxt[now][i]]];
                    q.push(nxt[now][i]);
                }
            }
        }
    }
    void query(const string& buf){
        int len=buf.size();
        int now = rt;
        for(int i=0;i<len;++i){
            now = nxt[now][buf[i]-'a'];
            int tmp=now;
            while(tmp!=rt){
                cnt[i] += ed[tmp];
                tmp=g[tmp];
            }
        }
    }
}a,b;
 
string t;
string s[maxn];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    int n;
    cin>>n;
    a.init();
    for(int i=1;i<=n;++i){
        cin>>s[i];
        a.insert(s[i]);
    }
    a.build();
    a.query(t);
    memcpy(cnt2,cnt,sizeof cnt);
    memset(cnt,0,sizeof cnt);
    b.init();
    for(int i=1;i<=n;++i){
        reverse(s[i].begin(),s[i].end());
        b.insert(s[i]);
    }
    b.build();
    reverse(t.begin(),t.end());
    b.query(t);
    ll ans=0;
    for(int i=0;i<t.size()-1;++i){
        ans += 1ll*cnt2[i]*cnt[t.size()-i-2];
    }
    cout<<ans;
    return 0;
}