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
|
#include "ssummary.h"
using namespace std;
ssummary::ssummary(int K):K(K) {bobhash=new BOBHash32(1000);}
void ssummary::clear()
{
memset(sum,0,sizeof(sum));
memset(last,0,sizeof(Next));
memset(Next2,0,sizeof(Next2));
rep(i,0,N)head[i]=Left[i]=Right[i]=0;
rep(i,0,len2-1)head2[0]=0;
tot=0;
rep(i,1,M+2)ID[i]=i;
num=M+2;
Right[0]=N;
Left[N]=0;
}
int ssummary::getid()
{
int i=ID[num--];
last[i]=Next[i]=sum[i]=Next2[i]=0;
return i;
}
int ssummary::location(string ST)
{
return (bobhash->run(ST.c_str(),ST.size()))%len2;
}
void ssummary::add2(int x,int y)
{
Next2[y]=head2[x];
head2[x]=y;
}
int ssummary::find(string s)
{
for(int i=head2[location(s)];i;i=Next2[i])
if(str[i]==s)return i;
return 0;
}
void ssummary::linkhead(int i,int j)
{
Left[i]=j;
Right[i]=Right[j];
Right[j]=i;
Left[Right[i]]=i;
}
void ssummary::cuthead(int i)
{
int t1=Left[i],t2=Right[i];
Right[t1]=t2;
Left[t2]=t1;
}
int ssummary::getmin()
{
if (tot<K) return 0;
if(Right[0]==N)return 1;
return Right[0];
}
void ssummary::link(int i,int ww)
{
++tot;
bool flag=(head[sum[i]]==0);
Next[i]=head[sum[i]];
if(Next[i])last[Next[i]]=i;
last[i]=0;
head[sum[i]]=i;
if(flag)
{
for(int j=sum[i]-1;j>0 && j>sum[i]-10;j--)
if(head[j]){linkhead(sum[i],j);return;}
linkhead(sum[i],ww);
}
}
void ssummary::cut(int i)
{
--tot;
if(head[sum[i]]==i)head[sum[i]]=Next[i];
if(head[sum[i]]==0)cuthead(sum[i]);
int t1=last[i],t2=Next[i];
if(t1)Next[t1]=t2;
if(t2)last[t2]=t1;
}
void ssummary::recycling(int i)
{
int w=location(str[i]);
if (head2[w]==i)
head2[w]=Next2[i];
else
{
for(int j=head2[w];j;j=Next2[j])
if(Next2[j]==i)
{
Next2[j]=Next2[i];
break;
}
}
ID[++num]=i;
}
//ssummary::~ssummary()
//{
//}
|
