【bzoj2865】字符串识别【bzoj1396】识别子串

Source and Judge

bzoj1396
bzoj2865

Record

2h

Analysis

请先思考后再展开

做法一:
sam求出出现一次的字符串
其形式一定是,知道右端点,然后长度至少为某个值后即出现一次
也就是说其贡献是min~right的区间取min和max~min的等差数列
离线后用单调队列(用并查集,按值从小到大处理也行)、栈即可
时间复杂度 $O(n)$
但过不了2865,被卡空间

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
#define pr pair<int,int>
#define FR first
#define SE second
const int MAX_N=110000;
char str[MAX_N];int len;
int ans[MAX_N];
struct DD
{
pr lis[MAX_N*2];
int tou,wei;DD(){tou=1;wei=0;}
void ins(pr a)
{
while(tou<=wei and lis[wei].FR>a.FR) wei--;
lis[++wei]=a;
}
int get(int pos)
{
while(tou<=wei and pos<lis[tou].SE) tou++;
if(tou<=wei) return lis[tou].FR;
else return INF;
}
}dd;//单调队列(用并查集,按值从小到大处理也行)
struct Sam
{
struct Nod
{
int son[30],nxt,mx;
int siz,right;
Nod() {memset(son,0,sizeof son);nxt=mx=siz=right=0;}
}p[MAX_N*2];
int id,lst,rt;Sam(){id=lst=rt=1;}
void add(int pos,int c)
{
int now=++id;
p[now].mx=p[lst].mx+1;
p[now].siz=1;p[now].right=pos;
int a=lst;
for(;a!=0 and p[a].son[c]==0;a=p[a].nxt) p[a].son[c]=now;
if(a==0) p[now].nxt=rt;
else
{
int b=p[a].son[c];
if(p[a].mx+1==p[b].mx) p[now].nxt=b;
else
{
int tmp=++id;
p[tmp]=p[b];p[tmp].mx=p[a].mx+1;
p[b].nxt=p[now].nxt=tmp;
for(;p[a].son[c]==b;a=p[a].nxt) p[a].son[c]=tmp;
}
}
lst=now;
}
int ct[MAX_N];
int lis[MAX_N*2];
void build()
{
memset(ct,0,sizeof ct);
for(int i=1;i<=id;i++) ct[p[i].mx]++;
for(int i=1;i<=len;i++) ct[i]+=ct[i-1];
for(int i=id;i>=1;i--) lis[ct[p[i].mx]--]=i;
for(int i=id;i>=1;i--)
{
int fa=p[lis[i]].nxt;
p[fa].siz+=p[lis[i]].siz;
p[fa].right=max(p[fa].right,p[lis[i]].right);
}
}
vector<int> tt[MAX_N];//等差数列
vector<pr> tt2[MAX_N];//区间取min
void solve()
{
for(int i=1;i<=id;i++) if(p[i].siz==1)
{
//printf("[%d,%d]->%d\n",p[i].right-p[i].mx+1,p[i].right-(p[p[i].nxt].mx+1)+1,p[i].right);
tt[ p[i].right-(p[p[i].nxt].mx+1)+1 ].push_back( p[p[i].nxt].mx+1 );
tt2[p[i].right].push_back(make_pair( p[p[i].nxt].mx+1,p[i].right-(p[p[i].nxt].mx+1)+1 ));
}
int now=INF;memset(ans,63,sizeof ans);
for(int i=len;i>=1;i--)
{
now++;
for(int t=0;t<(int)tt[i].size();t++) now=min(now,tt[i][t]);
for(int t=0;t<(int)tt2[i].size();t++) dd.ins(tt2[i][t]);
ans[i]=min(now,dd.get(i));
}
}
}sam;
void main()
{
scanf("%s",str+1);len=strlen(str+1);
for(int i=1;i<=len;i++) sam.add(i,str[i]-'a');
sam.build();
sam.solve();
for(int i=1;i<=len;i++) printf("%d\n",ans[i]);
}
};
int main()
{
srand(time(0));
mine::main();
}

做法二:
把sam换成sa即可节省空间,复杂度为nlogn

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/333f.html
转载请注明出处,谢谢!