【GDOI2013模拟4】贴瓷砖

题目

A镇的主街是由N个小写字母构成，镇长准备在上面贴瓷砖，瓷砖一共有M种，第i种上面有Li个小写字母，瓷砖不能旋转也不能被分割开来，瓷砖只能贴在跟它身上的字母完全一样的地方，允许瓷砖重叠，并且同一种瓷砖的数量是无穷的。

问街道有多少字母(地方)不能被瓷砖覆盖。

分析

AC自动机模板题，

优化：用up[x]表示x沿fail链上的第一个有值的点，这样就省去循环了 。

线段覆盖求答案。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=300001;

using namespace std;

struct ddx

{

	int c[26],fail,deep,w,sum,up;

}trie[4008000];

char s[N],s1[N];

int n,m,tot,ans,sum[N],d[N*14];

void put()

{

	int root=1;

	for(int i=1;i<=strlen(s1+1);i++)

	{

		if(trie[root].c[s1[i]-'a'])

		{

			root=trie[root].c[s1[i]-'a'];

			trie[root].sum++;

			if(i==strlen(s1+1))

			{

				trie[root].w++;

			}

		}

		else

		{

			trie[root].c[s1[i]-'a']=++tot;

			trie[tot].sum++;

			trie[tot].deep=trie[root].deep+1;

			root=tot;

			if(i==strlen(s1+1))

			{

				trie[tot].w++;

			}

		}

	}

}

void makefail()

{

	int head=0,tail=1,root=1;

	d[1]=1;

	trie[1].fail=0;

	while(head<tail)

	{

		int k=d[++head],p=0;

		for(int i=0;i<26;i++)

		{

			if(!trie[k].c[i]) continue;

			p=trie[k].c[i];

			int z=trie[k].fail;

			while(z && !trie[z].c[i])

				z=trie[z].fail;

			trie[p].fail=trie[z].c[i];

			d[++tail]=p;

			trie[p].fail=trie[p].fail?trie[p].fail:1;

			trie[p].up=p;

			if(trie[p].up!=1 && !trie[trie[p].up].w) trie[p].up=trie[trie[p].fail].up;

		}

	}

}

int find()

{

	int j=1;

	for(int i=1;i<=n;i++)

	{

		int index=s[i]-'a';

		while(j!=1 && !trie[j].c[index]) j=trie[j].fail;

		j=trie[j].c[index];

		j=j?j:1;

		int p=j;

		sum[i+1]--,sum[i-trie[trie[p].up].deep+1]++;

	}

}

int main()

{

	scanf("%d",&n);

	scanf("%s",s+1);

	scanf("%d",&m);

	tot++;

	for(int i=1;i<=m;i++)

	{

		scanf("%s",s1+1);

		put();

	}

	makefail();

	find();

	int k=0;

	for(int i=1;i<=n;i++)

	{

		k+=sum[i];

		if(k)

			ans++;

	}

	printf("%d",n-ans);

}