题目链接

ICPC2021沈阳站 E: Edward Gaming, the Champion

题意

输入一个字符串, 输出这个字符串中"edgnb"出现的次数。

题解

后缀自动机模板题。 将输入的字符串建立后缀自动机，从根节点开始沿 ->e->d->g->n->b 走。如果没有这个节点输出0。如果找到了这个节点，就输出这个节点endpos集合的大小。

代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = 400000 + 100;

struct Node {
    int len, fa;
    int ch[26];
} node[maxn];
int es[maxn];
int idx = 1, last = 1;
char s[maxn];

int q[maxn], c[maxn];

void extend(int c) {
    int p = last, np = ++idx;
    es[np] = 1;
    node[np].len = node[p].len + 1;
    for(;p && !node[p].ch[c]; p = node[p].fa) {
        node[p].ch[c] = np;
    }
    if(!p)
        node[np].fa = 1;
    else {
        int q = node[p].ch[c];
        if(node[q].len == node[p].len + 1) {
            node[np].fa = q;
        }else {
            int nq = ++idx;
            node[nq] = node[q];
            node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for(;p && node[p].ch[c] == q; p = node[p].fa)
                node[p].ch[c] = nq; 
        }
    }
    last = np;
}

int main() {
    scanf("%s", s);
    int n = strlen(s);
    for(int i = 0; i < n; i++)
        extend(s[i] - 'a');
    
    for(int i = 1; i <= idx; i ++)
        c[node[i].len] ++;
    for(int i = 1; i <= idx; i++)
        c[i] += c[i - 1];
    
    for(int i = idx; i >= 1; i--)
        q[c[node[i].len]--] = i;
    

    for(int i = idx; i >= 1; i--) {
        int u = q[i];
        es[node[u].fa] += es[u];
    }

    char T[] = "edgnb";
    int cur = 1;
    for(int i = 0; i < 5 && cur; i++)
        cur = node[cur].ch[T[i] - 'a'];
    es[0] = 0;
    printf("%d\n", es[cur]);
    return 0;
}

直接暴力也是可以过的

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
char s[N];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	int ans=0;
	for(int i=1;i<=n-4;i++){
		if(s[i]=='e'&&s[i+1]=='d'&&s[i+2]=='g'&&s[i+3]=='n'&&s[i+4]=='b'){
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}