【GDOI2013模拟4】贴瓷砖

2023-10-28 11:32

文章标签 模拟瓷砖 gdoi2013

本文主要是介绍【GDOI2013模拟4】贴瓷砖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意
给出 $n$ 个模式串和一个串 $S$ ，用这 $n$ 个模式串尽量多的覆盖 $S$ ，模式串之间可以重叠，求出最少有多少个位置没有被覆盖。

解法
这题有许多解法，下面列举两种：
1. 将所有模式串和要匹配的串 $S$ 反过来，然后做一次 $SA$ （后缀数组），然后，肆意恶搞。
2. 对 $S$ 做 $SA$ ，然后对于每一个匹配串都查找一下它在 $S$ 中可能的位置，标记一下，然后，肆意恶搞。

我想讲的解法
我想讲的解法是AC自动机（这在我之前的博客中有讲到），其实这题打AC自动机又快又简单，只要利用 $fail$ 数组增加一个 $len$ ，表示在用 $fail$ 弄出的这条链里，如果存在某些节点是一个模式串的结尾，那么 $len$ 即为这些模式串的长度的最大值，这样的实现仍然很简单。
最后，
肆意恶搞。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<cstring>
#include<queue>
#include<functional>
#include<set>
#include<map>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;const int MAXN = 300010;
const int MAXM = 5010;
const int MAXT = 5000010;int get(){char ch;while (ch=getchar(),(ch<'0'||ch>'9')&& ch!='-');char c=ch;int s=0;if (c!='-')s=c-48;while (ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-48;return c=='-'?-s:s;
}struct point{int fail,first;int len,col;
}h[MAXM*4000];
struct edge{int x,next;
}e[MAXM*4000];
int tot,n,m,len,ans,et;
int a[MAXN],f[MAXT],q[MAXN];
char s[MAXM];void addedge(int x,int y){e[++et].x=y;e[et].next=h[x].first;h[x].first=et;
}void inse(){int now=0;fo(i,1,len){int x(0);for(int p=h[now].first;p;p=e[p].next){if (h[e[p].x].col==s[i]){x=e[p].x;break;}}if(!x)x=++tot,addedge(now,x),h[x].col=s[i];now=x;}h[now].len=len;
}int find(int x,int col){for(int p=h[x].first;p;p=e[p].next)if (h[e[p].x].col==col)return e[p].x;return 0;
}void get_fail(){int head(0),tail(0);for(int p=h[0].first;p;p=e[p].next){f[++tail]=e[p].x;}while (head<tail){int x=f[++head];for(int p=h[x].first;p;p=e[p].next){int y=e[p].x;int i=h[y].col;int now=h[x].fail;while(now&&!find(now,i))now=h[now].fail;int v=find(now,i);if (v)h[y].fail=v,h[y].len=max(h[y].len,h[h[y].fail].len);f[++tail]=y;}}
}void work(){ans=0;int now=0;fo(i,1,n){while(now&&!find(now,a[i]))now=h[now].fail;int x=find(now,a[i]);if (x){now=x;q[i]=max(q[i],h[now].len);}}int x=0;fd(i,n,1){x=max(x-1,q[i]);q[i]=x;}for(int i=n;i;){if (!q[i])ans++,i--;else i-=q[i];}
}int main(){n=get();tot=0;fo(i,1,n){char ch;while (ch=getchar(),ch<'a'||ch>'z');a[i]=ch-'a';}m=get();fo(i,1,m){char ch;while(ch=getchar(),ch<'a'||ch>'z');s[len=1]=ch-'a';while(ch=getchar(),ch>='a'&&ch<='z')s[++len]=ch-'a';inse();}get_fail();work();printf("%d\n",ans);
}