SP8093 JZPGYZ - Sevenk Love Oimaster

发表于 | 评论数： | 阅读次数：
本文字数： 5.4k | 阅读时长 ≈ 5 分钟

SP8093 JZPGYZ - Sevenk Love Oimaster

传送门

洛谷

题意描述

Oimaster and sevenk love each other.
But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman’s nature, s
evenk felt angry and began to check oimaster’s online talk with ChuYuXun. Oimaster talked with Ch
uYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, “how many strings in oimaster’s online talk contain this string as their substrings?
题目大意：给定n个模板串，以及m个查询串，依次查询每一个查询串是多少个模板串的子串

输入输出格式

输入格式：

There are two integers in the first line, the number of strings n and the number of questions q. And n lines follow, each of them is a string describing oimaster’s online talk. And q lines follow, each of them is a question.n<=10000, q<=60000 the total length of n strings<=100000, the total length of q question strings<=360000

输出格式：

For each question, output the answer in one line.

输入输出样例

输入样例#1：

3 3
abcabcabc
aaa
aafe
abc
a
ca

输出样例#1：

1
3
1

说明

【样例解释1】

$abc$在$abcabcabc$中出现了，所以第一个询问答案为1。

$a$在三个字符串中都出现了，所以第二个询问答案为3。

$ca$只在$abcabcabc$中出现了，所以第三个询问的答案为1。

分析

这是一道广义$SAM$模板题。
本来想打一打来练手，但似乎出了锅。
具体的说：
我打了一份枚举子串更新$SAM$的代码，过了。
忽然想起，似乎还可以在插入时更新$SAM$，打了以后，挂了。
不知道是根本不能这样做还是我哪里打挂了，请大佬帮忙查一下错，谢谢！

代码

插入时更新$SAM$然后挂了的代码。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100010
#define maxm 360010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,m,las,cnt=1,fa[maxn<<1],vis[maxn<<1],len[maxn<<1],val[maxn<<1],ch[maxn<<1][26];
char str[maxm];
void add(int cc,int pos)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	for(;p&&!ch[p][cc];p=fa[p])ch[p][cc]=np;
	if(!p)fa[np]=1;
	else
	{
		int q=ch[p][cc];
		if(len[q]==len[p]+1)fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			fa[nq]=fa[q];
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[q]=fa[np]=nq;
			for(;p&&ch[p][cc]==q;p=fa[p])ch[p][cc]=nq;
		}
	}
	for(;np&&vis[np]!=pos;np=fa[np])
		vis[np]=pos,val[np]+=1;
}
int main()
{
	read(n,m);
	for(int i=1;i<=n;i++)
	{
		las=1;
		scanf("%s",str);
		int len=strlen(str);
		for(int j=0;j<len;j++)
			add(str[j]-'a',i);
	}
	for(int i=1;i<=m;i++)
	{
		int now=1,flag=true;
		scanf("%s",str);
		int len=strlen(str);
		for(int j=0;j<len;j++)
		{
			if(!ch[now][str[j]-'a'])
			{
				flag=false;
				puts("0");
				break;
			}
			now=ch[now][str[j]-'a'];
		}
		if(flag)printf("%d\n",val[now]);
	}
    return 0;
}

枚举子串更新的代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100010
#define maxm 10010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,m,las,cnt=1,fa[maxn<<1],vis[maxn<<1],len[maxn<<1],val[maxn<<1],ch[maxn<<1][26];
string str[maxm];
void add(int cc)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	for(;p&&!ch[p][cc];p=fa[p])ch[p][cc]=np;
	if(!p)fa[np]=1;
	else
	{
		int q=ch[p][cc];
		if(len[q]==len[p]+1)fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			fa[nq]=fa[q];
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[q]=fa[np]=nq;
			for(;p&&ch[p][cc]==q;p=fa[p])ch[p][cc]=nq;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		las=1;
		cin>>str[i];
		for(int j=0;j<(int)str[i].length();j++)
			add(str[i][j]-'a');
	}
	for(int i=1;i<=n;i++)
	{
		int now=1;
		for(int j=0;j<(int)str[i].length();j++)
		{
			now=ch[now][str[i][j]-'a'];
			int tmp=now;
			while(tmp&&vis[tmp]!=i)
			{
				vis[tmp]=i;
				val[tmp]+=1;
				tmp=fa[tmp];
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		int now=1,flag=true;
		cin>>str[0];
		for(int j=0;j<(int)str[0].length();j++)
		{
			if(!ch[now][str[0][j]-'a'])
			{
				flag=false;
				puts("0");
				break;
			}
			now=ch[now][str[0][j]-'a'];
		}
		if(flag)printf("%d\n",val[now]);
	}
    return 0;
}