字符串

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 310 阅读时长 ≈ 1 分钟

题意：

给定一个字符串，求包含ACCEPT但不包含WA且长度大于k的子串数量。

题解：

子序列自动机，一个我较少写的算法（ps:可能是用到了没意识到），mark。。。

子序列自动机的基本概念是用二维数组保存对于i位置 j字符第一次出现的位置为nxt[i][j]，通过这种方式来维护字串ACCEPT和子串WA的子序列位置。

这是一个很容易理解，很多人没有给它命名的算法。该题的答案就是对于每个以i结尾的字符串i，计算后一个“WA"，“A”与后一个“ACCEPT”中的“A”的上一位合法字符串长度累和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void get_next(){
    for(int i=n;i>=0;i--){
        for(int j=0;j<26;j++){
            if(i==n) nxt[i][j]=n;
            else nxt[i][j]=nxt[i+1][j];
        }
        if(i!=n) nxt[i][s[i]-'A']=i;
    }
}

int get_pos(int st,string s){
    int first=1;
    for(auto ch:s){
        if(first) st=nxt[st][ch-'A'];
        else st=nxt[st+1][ch-'A'];
        first=0;
        if(st==n) return st;
    }
    return st;
}

void slove(){
    cin>>n>>k>>s;
    get_next();
    string ac="ACCEPT",wa="WA";
    ll ans=0;
    for(int i=0;i<n;i++){
        int r1=get_pos(i,ac),r2=get_pos(i,wa);
        r1=max(r1,i+k-1);
        ans=ans+max(r2-r1,0ll);
    }
    cout<<ans<<endl;
}