洛谷的板子

题目1

标程

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
#include<iostream>
#include<queue>
#define maxn 1000001
using namespace std;
bool b[maxn];
string word,s;
int ans=0;
typedef struct A{
A *fail;
A *next[26];
int word;
int num;
void a(){
for(int i=0;i<26;i++){
next[i]=NULL;
}
fail=NULL;
word=0;
num=0;
}
}node;
node *root;
void insert_word(int j){
int len=word.length();
node *p=root;
for(int i=0;i<len;i++){
int k=word[i]-'a';
if(p->next[k]==NULL){
node *temp;
temp=new node;
temp->a();
p->next[k]=temp;
}
p=p->next[k];
}
p->word=j;
p->num++;
}
void fail(){
queue<node *>q;
q.push(root);
while(!q.empty()){
node *p=q.front();
q.pop();
for(int i=0;i<26;i++){
if(p->next[i]!=NULL){
node *t=p->next[i];
if(p==root){
t->fail=root;
}
else{
node *fafail=p->fail;
while(fafail!=NULL){
if(fafail->next[i]!=NULL){
t->fail=fafail->next[i];
break;
}
fafail=fafail->fail;
}
if(fafail==NULL)t->fail=root;
}
q.push(t);
}
}
}
}
void query(){
int len=s.length();
node *p=root;
for(int i=0;i<len;i++){
int k=s[i]-'a';
while(p!=root&&p->next[k]==NULL)
p=p->fail;
p=p->next[k];
if(p==NULL)
p=root;
node *temp=p;
//while(temp!=root){
if(temp->word&&!b[temp->word]){
b[temp->word]=1;
ans+=temp->num;
}
// temp=temp->fail;
//}
}
}
/*
int c[10001];
int all=0;
void print(){
for(int i=1;i<=all;i++){
printf("%c",b[i]+'a');
}
cout<<endl;
}
void dfs(node *t){
if(t->word)print();
for(int i=0;i<26;i++){
if(t->next[i]!=NULL){
c[++all]=i;
dfs(t->next[i]);
all--;
}
}

}*/
int main(){
//freopen("P3808.in","r",stdin);
//freopen("P3808.out","w",stdout);
root=new node;
root->a();
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>word;
insert_word(i);
}
//dfs(root);

fail();
while(cin>>s){
ans=0;
query();
cout<<ans<<endl;
}
}

题目2

标程

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
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef struct A{
int word;
A* fail;
A* next[26];
void aaa(){
word=0;
fail=NULL;
for(int i=0;i<26;i++)
next[i]=NULL;
}
}node;
node *root;
queue<node*>q;
map<string,int>tmap;
string word[200];
char t[1000010];
int num[200];
void insert(int x){
node *p=root;
int len=word[x].length();
for(int i=0;i<len;i++){
int k=word[x][i]-'a';
if(p->next[k]==NULL){
node *new_node=new node;
new_node->aaa();
p->next[k]=new_node;
}
p=p->next[k];
}
p->word=x;
}
void build_fail(){
q.push(root);
while(!q.empty()){
node *p=q.front();
q.pop();
for(int i=0;i<26;i++){
if(p->next[i]!=NULL){
node *k=p->next[i];
q.push(k);
if(p==root){
k->fail=root;
}
else{
node *fafail=p->fail;
while(fafail!=NULL){
if(fafail->next[i]!=NULL){
k->fail=fafail->next[i];
break;
}
fafail=fafail->fail;
}
if(fafail==NULL)k->fail=root;
}
}
}
}
}
void query(){
int len=strlen(t);
node *p=root;
for(int i=0;i<len;i++){
int k=t[i]-'a';
while(p->next[k]==NULL&&p!=root)p=p->fail;
p=p->next[k];
if(p==NULL)p=root;
else{
node *temp=p;
while(temp!=root){
if(temp->word){
num[temp->word]++;
}
temp=temp->fail;
}
}
}
}
int cmp1(int a,int b){
return a>b;
}
int cmp(string a,string b){
if(num[tmap[a]]==num[tmap[b]])return tmap[a]<tmap[b];
return num[tmap[a]]>num[tmap[b]];
}
int main(){
//freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n)&&n){
memset(num,0,sizeof(num));
tmap.clear();
root=new node;
root->aaa();
for(int i=1;i<=n;i++){
cin>>word[i];
tmap[word[i]]=i;
insert(i);
}
build_fail();
scanf("%s",t);
query();
sort(word+1,word+1+n,cmp);
sort(num+1,num+1+n,cmp1);
int maxnum=num[1];
cout<<maxnum<<endl;
for(int i=1;i<=n;i++){
if(num[i]==maxnum){
cout<<word[i]<<endl;
}
}
}
return 0;
}

题目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
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 2e6 + 5;
struct node{
int word;int deg,val;
node *fail , *next[26];
node() {
word = deg = val = 0;fail = NULL;
for (int i = 0;i < 26;i++)
next[i] = NULL;
}
}*ext=(node*)malloc(sizeof(node)*maxn),*root;

queue<node*> Q;
char t[maxn], word[maxn];int num[maxn],ans[maxn];

inline node* Ot(){return *ext=node(),ext++;}

void insert(int x) {
node* p = root;
int len = strlen(word);
for (int i = 0;i < len;i++) {
int k = word[i] - 'a';
if (p->next[k] == NULL) {
p->next[k] = Ot();
}
p = p->next[k];
}
if (!p->word) {
p->word = x;
}
num[x] = p->word;
}
void build_fail() {
for(int i=0;i<26;i++) if(root->next[i]) root->next[i]->fail=root,Q.push(root->next[i]); else root->next[i]=root;
while (!Q.empty()) {
node* p = Q.front();Q.pop();
// printf("%ld\n",p-root);
for (int i = 0;i < 26;i++) {
if (p->next[i]) {
p->next[i]->fail = p->fail->next[i],p->fail->next[i]->deg++;
if(p->next[i]!=root) Q.push(p->next[i]);
}
else p->next[i] = p->fail->next[i];
}
}
}

void query() {
int len = strlen(t);
// printf("len:%d\n",len);
node* p = root;
for (int i = 0;i < len;i++) {
// printf("i:%d p:%ld np:%ld\n",i,p-root,p->next[t[i]-'a']);
int k = t[i] - 'a';
p=p->next[k];p->val++;
}
// puts("OUT");
}

void topo(){
for(node *i=root;i<ext;i++) if(!i->deg) Q.push(i);
while(!Q.empty()){
node *p=Q.front();Q.pop();ans[p->word]=p->val;
// printf("p:%ld\n",p-root);
if(p!=root){
p->fail->val += p->val;
if(--p->fail->deg==0) Q.push(p->fail);
}
}
}

int main() {
int n;scanf("%d", &n);root=Ot();
for (int i = 1;i <= n;i++) {
scanf("%s", word);
insert(i);
}
build_fail();
scanf("%s", t);
query();topo();
for (int i = 1;i <= n;i++) {
cout<<ans[num[i]]<<endl;
}
return 0;
}