洛谷 3966 libreoj10060 [TJOI2013]单词 题解

发表于 | 更新于 | 阅读次数：
本文字数： 753 字 | 阅读时长 ≈ 3 分钟

题意简述

给定个单词，对每个单词求出个单词中总共包含多少这个单词（自己也算，也就是说答案至少为）。比如三个单词分别是，那么出现次（自己一次，中两次）。

思路

每个字符接在一起，中间插入一个特殊字符，然后跑一遍自动机即珂。

具体的思维过程

自动机的模板问题：给定一个文本串，和一些模式串，求每个模式串在文本串中出现了多少次。

实际上我们珂以把这个问题转化成模板问题。由于我们的匹配不能跨单词，只能限于每个单词之间。最好的解决方法就是构造这样的情况：跨单词肯定得失配。

这好办，只要把所有单词接在一起，然后在中间加一个特殊字符，使得它不等于中的任意一个，那跨单词的时候肯定就失配了（因为模式串中只有）比如说设成中的字符，经验证，这个字符是左大括号。然后写自动机的时候，就当字母有个字母去建树即珂。这题就被完美的套成了模板解决了。

代码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 212345

	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define Tra(i,u) for(int i=G.Start(u);~i;i=G.Next(i))
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)

	int id[N];
	class AC_Automaton
	{
	public:
		int tr[N][27];
		int tot;

		void Init()
		{
			FK(tr);
			tot=1;
		}
		int Insert(char s[])
		{
			int pos=1;
			F(i,0,INT_MAX)
			{
				if (!s[i]) break;

				int c=s[i]-'a';
				if (!tr[pos][c])
				{
					tr[pos][c]=++tot;
				}
				pos=tr[pos][c];
			}
			return pos;
		}

		int fail[N];
		queue<int> Q;
		vector<int> G[N];void Add(int u,int v){G[u].push_back(v);}
		void BuildFail()
		{
			while(!Q.empty()) Q.pop();

			F(i,0,26) tr[0][i]=1;
			Q.push(1);
			while(!Q.empty())
			{
				int u=Q.front();Q.pop();

				F(i,0,26)
				{
					if (tr[u][i])
					{
						fail[tr[u][i]]=tr[fail[u]][i];
						Q.push(tr[u][i]);
					}
					else tr[u][i]=tr[fail[u]][i];
				}
			}

			F(i,2,tot) Add(fail[i],i);
		}

		int size[N];
		void DFS(int u)
		{
			F(i,0,(int)G[u].size()-1)
			{
				int v=G[u][i];
				DFS(v);
				size[u]+=size[v];
			}
		}
		void Query(char s[])
		{
			int pos=1;
			F(i,0,INT_MAX)
			{
				if (!s[i]) break;

				int c=s[i]-'a';
				pos=tr[pos][c];
				++size[pos];
			}
			DFS(1);
		}
	}AC;

	int n;
	char s[N];
	char T[N*10];
	void Input()
	{
		scanf("%d",&n);
		AC.Init();
		FK(T);
		F(i,1,n)
		{
			scanf("%s",s);
			id[i]=AC.Insert(s);
			strcat(T,s);
			strcat(T,"{");//'{'='z'+1
		}
	}
	void Soviet()
	{
		// printf("T=%s\n",T);
		AC.BuildFail();
		AC.Query(T);
		F(i,1,n)
		{
			printf("%d\n",AC.size[id[i]]);
		}
	}
	void IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}

w