UESTC 8 God Only Knows! AC自动机

God Only Knows! AC自动机

Source

The 11th UESTC Programming Contest Final

UESTC 8 God Only Knows!

My Solution

题意：给一个字符串s，然后给出n个字符串stri，问s的不包含任意stri串的子串的个数。

AC自动机

做了一晚上，终于用自己的方法过了，开心 Y ^ _ ^ Y。

先用给出的n个串stri来建立AC自动机，其中在朴素AC自动机的基础上添加一个depth[MAX_SIZE]成员用来记录每个节点的深度。

然后根据主串s在自动机上跑，碰到危险节点(即danger节点，给定串stri的结尾节点是危险节点或者该节点的后缀节点是危险节点的节点)时，

维护lastdanger 表示主串s已经出现过的stri中最靠近i的危险串在主串上的起点(即给定串的某个起点)，这个可以先遇到危险节点，

然后用该节点的深度ac.depth[now]来求出该危险串的起点，然后维护lastdanger。

且当前节点是危险节点时，用fail指针访问该节点的后缀节点，如果新的节点还是危险节点则继续维护lastdanger，并继续访问当前节点的后缀节点，

直到访问到非danger节点时，才继续在自动机上遍历主串的下一个字符。

if(ac.danger[now]){

while(ac.danger[now]){

lastdanger = max(lastdanger, i - ac.depth[now] + 1);

now = ac.fail[now];

}

在主串中没访问一个字符时ans += (LL)(i - lastdanger);//lastdanger 初始化为-1

比如

abcdefg

0123456//这个是上面字符串的下标
2
bcd
ef

当访问012时没有碰到危险节点，当遍历到3即d时，碰到了危险节点这是要更新lastdanger为1，然后遍历到5即f时又要更新lastdanger，

ans = 0 - (-1), + 1 - (-1), + 2 - (-1), + 3 - 1, + 4 - 1, + 5 - 4, + 6 - 4 == 14;

复杂度 O(T*n)

#include 
#include 
#include 
#include 
#include 
#include 





using namespace std;
typedef long long LL;
const int CHAR_SIZE = 26;
const int MAX_SIZE = 1e5 + 8;
map<char, int> mp;

struct AC_Machine{
    int ch[MAX_SIZE][CHAR_SIZE], danger[MAX_SIZE], fail[MAX_SIZE];
    int depth[MAX_SIZE];
    int sz;

    void init(){
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        memset(danger, 0, sizeof danger);//
        memset(fail, 0, sizeof fail);
        memset(depth, 0, sizeof depth);
    }

    void _insert(const string &s){
        int n = s.size();
        int u = 0, c;
        for(int i = 0; i < n; i++){
            c = mp[s[i]];
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof ch[sz]);
                danger[sz] = 0;
                depth[sz] = i+1;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        danger[u] = 1;
    }

    void _build(){
        queue Q;
        fail[0] = 0;
        for(int c = 0, u; c < CHAR_SIZE; c++){
            u = ch[0][c];
            if(u){Q.push(u); fail[u] = 0;}
        }
        int r;
        while(!Q.empty()){
            r = Q.front();
            Q.pop();
            danger[r] |= danger[fail[r]];
            for(int c = 0, u; c < CHAR_SIZE; c++){
                u = ch[r][c];
                if(!u){ch[r][c] = ch[fail[r]][c]; continue; }
                fail[u] = ch[fail[r]][c];
                Q.push(u);
            }
        }
    }
}ac;

string s, str;

int main()
{
    #ifdef LOCAL
    freopen("2.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    int T, n, len, now, i, lastdanger, kase = 1;
    LL ans;
    for(int i = 0; i < 26; i++){mp[(i + 'a')] = i;} cin >> T;
    while(T--){
        cin >> s;
        cin >> n;
        ac.init();
        while(n--){
            cin >> str;
            ac._insert(str);
        }
        ac._build();

        ans = 0;
        len = s.size();
        now = 0;
        lastdanger = -1;
        for(i = 0; i < len; i++){
            now = ac.ch[now][mp[s[i]]];
            if(ac.danger[now]){
                while(ac.danger[now]){
                    lastdanger = max(lastdanger, i - ac.depth[now] + 1);
                    now = ac.fail[now];
                }
            }
            ans += (LL)(i - lastdanger); //
        }

        cout << "Case #" << kase << ": " << ans << "n";
        kase++;
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

UESTC 8 God Only Knows! AC自动机

God Only Knows! AC自动机

Source

My Solution

相关推荐

Gym – 101164C Castle KMP的拓展、next数组+dp、好题

HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置

HDU – 2222 Keywords Search AC自动机

UESTC 1384 卿大爷的多个女友后缀数组、最长连续重复子串

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 8 God Only Knows! AC自动机

God Only Knows! AC自动机

Source

My Solution

相关推荐

Gym – 101164C Castle KMP的拓展、next数组+dp、好题

HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置

HDU – 2222 Keywords Search AC自动机

UESTC 1384 卿大爷的多个女友 后缀数组、最长连续重复子串

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1384 卿大爷的多个女友后缀数组、最长连续重复子串