SPOJ – hahaschool

BZOJ 2780 / SPOJ JZPGYZ Sevenk Love Oimaster

September 04, 20152015-09-04hahaschoolLeave a comment

题意

给出一系列的字符串，我们把这些串叫母串，然后给你若干字符串，对于每一个字符串，你要求出在多少个母串中可以找到和给出的字符串相同的母串的字串。

思路

子串问题，要借助后缀系列解决，这个题使用了后缀自动机。但是通常意义的后缀自动机都是针对一个母串建立的，现在我们手里有一堆母串，这时候就需要我们进行活用，来创建“广义后缀自动机”，这个自动机将可以接受母串集合里所有的字串。

广义后缀自动机的建立方法其实是在一般的自动机创建基础之上，增加了一些东西。构造后缀自动机的方法是增量法，构造广义后缀自动机的方法也是一样的，但是我们从第个二串开始，一位一位增量的时候，我们有可能会用到构造到一半的自动机的某些节点或者某些转移边。对于当前将要加入的mxn(最长可接受字串长度)值，和当前追加节点时的last，如果last有一条转移边可以用，而且即将加入的新节点的mxn值正好等于last的mxn+1，这说明既存的节点和我们将要加入的节点是等价的，这一轮的追加到这里就可以结束了。如果存在转移边，但是转移边连着的节点mxn值并不是last的mxn+1，这个时候就需要我们使用在平常构造后缀自动机中使用的“拆点”方法。复制既存的节点作为符合我们mxn要求的节点，调整parent关系和所有自动机上父亲节点的转移关系，就像我们在平常构造自动机时为了防止mxn异常缩短采用的“拆点”方法一样。如果last节点不存在可用的转移边，这时候按照普通的增量法处理就可以。(如果觉得费解，不妨直接参考我的MultiSAM_Append()方法)。

创建完广义后缀自动机，这还只是个开始。接下来我们要提取出自动机中的所有的parent关系，创建parent树。我们注意到，在parent树中，一个节点的子树代表的是以这个节点为后缀的全部字串。举个例子就是，对于“banana”的”ana”代表节点(mxn值3)，他的子树就代表了”ana“,”nana“,”bana“,”anana“,”banana“，这一系列字串。这一特性有什么用呢？

注意到题意，我们要找到给出的串在多少个串中匹配，如果我们按照正常的方法在广义后缀自动机上完整地匹配这个串（如果匹配有中断，那就说明这个串不存在于母串集合的字串当中），这个时候转移到的最终状态对应节点的parent树的子树，就是在母串集合中所有的以给出的串为后缀的字串。如果我们给parent树上的每一个节点挂一个列表，标记这个节点都被哪些字符串利用了，这样只要我们逐一统计子树中的每一个节点，就可以知道当前给出的串在几个母串中存在，问题就可以解决了。

但是对于每一棵子树都统计一次，复杂度很大，显然需要再优化。优化的方法就是“DFS序把树压平”然后“离线处理”。首先遍历parent树，纪录每一个节点进入时的DFN和出去时的DFN，从进去到出去这两个DFN之间的所有节点(包括出入两个节点)显然就是parent的子树了。现在我们的问题就转变为了在某个数组上一段给定的区间求有多少个不同的数字，而且还是离线处理，这种问题可以使用一种O(n)的处理方法，详情可以参考BZOJ 1878 HH的项链。

问题到了这里，终于是完美地解决了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const int MAXN = 200010;

int tot = 0;

#pragma mark - Binary Indexed Tree (BIT) 1D
//index begins from ONE
//init:memset BIT,set BIT_size
int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int
int BIT_size;//should assign when use

inline int lowbit(int a){
    return a & (-a);
}

void BIT_modify(int pos,int delta){//type of delta may need to modify
    for (int x = pos; x <= BIT_size; x += lowbit(x)) {
        BIT[x] += delta;
    }
}

int BIT_sum(int pos){//return type may alter
    int ret = 0;
    for (int x = pos; x > 0; x -= lowbit(x)) {
        ret += BIT[x];
    }
    return ret;
}
#pragma mark -

struct Graph{//Chained Linear Edges
    int head[MAXN];
    int next[MAXN];
    int to[MAXN];
    inline void addEdge(int _from,int _to){
        static int q = 1;//!!
        to[q] = _to;
        next[q] = head[_from];
        head[_from] = q++;
    }
} parentTree,idx;

struct Query{
    int id,ans,from,to;
} query[60010];

bool cmp1(const Query &a,const Query &b){
    return a.to < b.to;
}

bool cmp2(const Query &a,const Query &b){
    return a.id < b.id;
}


struct SAM_State{
    int mxn;
    int id;
    SAM_State *to[26];
    SAM_State *parent;
    SAM_State(int _mxn){
        mxn = _mxn;
        id = ++tot;
        memset(to, 0, sizeof(to));
        parent = NULL;
    }
} *state[MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = new SAM_State(p -> mxn + 1);
    state[np -> id] = np;
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            state[nq -> id] = nq;
            nq -> parent = q -> parent;
            q -> parent = nq;
            np -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

SAM_State* MultiSAM_Append(SAM_State *last, SAM_State *root,int ch){
    SAM_State *p = last;
    if (p -> to[ch] != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            last = q;
        }else {
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            state[nq -> id] = nq;
            nq -> parent = q -> parent;
            q -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
            last = nq;
        }
    }else{
        return SAM_Append(last, root, ch);
    }
    return last;
}

void MultiSAM_Build(int num,char* str,SAM_State *root){
    SAM_State *last = root;
    int len = (int)strlen(str);
    for (int i = 0; i < len; i++) {
        last = MultiSAM_Append(last, root, str[i] - 'a');
        idx.addEdge(last -> id, num);
    }
}

SAM_State* SAM_Match(char *str,SAM_State *root){//only for this problem
    SAM_State *sam = root;
    int len = (int)strlen(str);
    for (int i = 0; i < len; i++) {
        if (sam -> to[str[i] - 'a']) {
            sam = sam -> to[str[i] - 'a'];
        }else{
            return NULL;
        }
    }
    return sam;
}

int in[MAXN],out[MAXN],seq[MAXN],dfn = 0;//dfn begins from 1
void dfs_getdfn(int cur){
    in[cur] = ++dfn;
    seq[dfn] = cur;
    for (int i = parentTree.head[cur]; i; i = parentTree.next[i]) {
        dfs_getdfn(parentTree.to[i]);
    }
    out[cur] = dfn;
}

char container[360010];
int prv[MAXN];
int main(){
    int n,m;
    scanf(" %d %d",&n,&m);
    state[1] = new SAM_State(0);
    for (int i = 1; i <= n; i++) {
        scanf(" %s",container);
        MultiSAM_Build(i,container, state[1]);
    }

    for (int i = 1; i <= tot; i++) {
        if (state[i] -> parent) {
            parentTree.addEdge(state[i] -> parent -> id, state[i] -> id);
        }
    }
    dfs_getdfn(1);
    for (int i = 1; i <= m; i++) {
        scanf(" %s",container);
        SAM_State *pos = SAM_Match(container, state[1]);
        if (pos != NULL) {
            query[i].id = i;
            query[i].from = in[pos -> id];
            query[i].to = out[pos -> id];
        }else{
            query[i].id = i;
            query[i].from = -1;
            query[i].to = -1;
        }
    }
    sort(query+1, query+1+m, cmp1);

    BIT_size = tot;
    int k = 1;
    while (query[k].to == -1) {
        k++;
    }
    for (int i = 1; i <= tot; i++) {
        for (int j = idx.head[seq[i]]; j; j = idx.next[j]) {
            if (prv[idx.to[j]]) {
                BIT_modify(prv[idx.to[j]], -1);
            }
            BIT_modify(prv[idx.to[j]] = i, 1);
        }
        for (; i == query[k].to && k <= m; k++) {
            query[k].ans = BIT_sum(query[k].to) - BIT_sum(query[k].from - 1);
        }
    }
    sort(query+1, query+1+m, cmp2);
    for (int i = 1; i <= m; i++) {
        printf("%d\n",query[i].ans);
    }

    return 0;
}

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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

const int MAXN = 200010;

int tot = 0;

#pragma mark - Binary Indexed Tree (BIT) 1D

//index begins from ONE

//init:memset BIT,set BIT_size

int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int

int BIT_size;//should assign when use

inline int lowbit(int a){

return a & (-a);

}

void BIT_modify(int pos,int delta){//type of delta may need to modify

for (int x = pos; x <= BIT_size; x += lowbit(x)) {

BIT[x] += delta;

}

int BIT_sum(int pos){//return type may alter

int ret = 0;

for (int x = pos; x > 0; x -= lowbit(x)) {

ret += BIT[x];

}

return ret;

}

#pragma mark -

struct Graph{//Chained Linear Edges

int head[MAXN];

int next[MAXN];

int to[MAXN];

inline void addEdge(int _from,int _to){

static int q = 1;//!!

to[q] = _to;

next[q] = head[_from];

head[_from] = q++;

}

} parentTree,idx;

struct Query{

int id,ans,from,to;

} query[60010];

bool cmp1(const Query &a,const Query &b){

return a.to < b.to;

}

bool cmp2(const Query &a,const Query &b){

return a.id < b.id;

}

struct SAM_State{

int mxn;

int id;

SAM_State *to[26];

SAM_State *parent;

SAM_State(int _mxn){

mxn = _mxn;

id = ++tot;

memset(to, 0, sizeof(to));

parent = NULL;

}

} *state[MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = new SAM_State(p -> mxn + 1);

state[np -> id] = np;

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = new SAM_State(p -> mxn + 1);

state[nq -> id] = nq;

nq -> parent = q -> parent;

q -> parent = nq;

np -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

SAM_State* MultiSAM_Append(SAM_State *last, SAM_State *root,int ch){

SAM_State *p = last;

if (p -> to[ch] != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

last = q;

}else {

SAM_State *nq = new SAM_State(p -> mxn + 1);

state[nq -> id] = nq;

nq -> parent = q -> parent;

q -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

last = nq;

}

}else{

return SAM_Append(last, root, ch);

}

return last;

}

void MultiSAM_Build(int num,char* str,SAM_State *root){

SAM_State *last = root;

int len = (int)strlen(str);

for (int i = 0; i < len; i++) {

last = MultiSAM_Append(last, root, str[i] - 'a');

idx.addEdge(last -> id, num);

}

SAM_State* SAM_Match(char *str,SAM_State *root){//only for this problem

SAM_State *sam = root;

int len = (int)strlen(str);

for (int i = 0; i < len; i++) {

if (sam -> to[str[i] - 'a']) {

sam = sam -> to[str[i] - 'a'];

}else{

return NULL;

}

return sam;

}

int in[MAXN],out[MAXN],seq[MAXN],dfn = 0;//dfn begins from 1

void dfs_getdfn(int cur){

in[cur] = ++dfn;

seq[dfn] = cur;

for (int i = parentTree.head[cur]; i; i = parentTree.next[i]) {

dfs_getdfn(parentTree.to[i]);

}

out[cur] = dfn;

}

char container[360010];

int prv[MAXN];

int main(){

int n,m;

scanf(" %d %d",&n,&m);

state[1] = new SAM_State(0);

for (int i = 1; i <= n; i++) {

scanf(" %s",container);

MultiSAM_Build(i,container, state[1]);

}

for (int i = 1; i <= tot; i++) {

if (state[i] -> parent) {

parentTree.addEdge(state[i] -> parent -> id, state[i] -> id);

}

dfs_getdfn(1);

for (int i = 1; i <= m; i++) {

scanf(" %s",container);

SAM_State *pos = SAM_Match(container, state[1]);

if (pos != NULL) {

query[i].id = i;

query[i].from = in[pos -> id];

query[i].to = out[pos -> id];

}else{

query[i].id = i;

query[i].from = -1;

query[i].to = -1;

}

sort(query+1, query+1+m, cmp1);

BIT_size = tot;

int k = 1;

while (query[k].to == -1) {

k++;

}

for (int i = 1; i <= tot; i++) {

for (int j = idx.head[seq[i]]; j; j = idx.next[j]) {

if (prv[idx.to[j]]) {

BIT_modify(prv[idx.to[j]], -1);

}

BIT_modify(prv[idx.to[j]] = i, 1);

}

for (; i == query[k].to && k <= m; k++) {

query[k].ans = BIT_sum(query[k].to) - BIT_sum(query[k].from - 1);

}

sort(query+1, query+1+m, cmp2);

for (int i = 1; i <= m; i++) {

printf("%d\n",query[i].ans);

}

return 0;

}

SPOJ SUBLEX Lexicographical Substring Search

August 20, 20152015-08-20hahaschoolLeave a comment

题意

把一个字符串所有的不同的字串全拿出来，按字典序排序，第k小的字符串是什么样子的呢？

思路

字串问题当然是后缀自动机了。对于给出的字符串，建立一个后缀自动机，然后对后缀自动机对应的状态图进行一次拓扑排序，每个节点的深度就是节点上携带的mxn(当前状态对应的字串最长为多少位)。接下来我们从深度最大的节点开始往根部处理每一个节点，我们要求出的就是对于每个能走的边，所有接下来的以这条边对应的字母开头的字串数目，而节点上面存的是节点出边的边权之和。这样我们就得到了一个处理好的图，我们只要在这个图上面搜索，逼近k值就可以了。

因为SPOJ卡常数特别严重，所以拓扑排序要使用计数排序的方法，而且要开额外的数组纪录每一个节点所有的孩子来加快之后的搜索速度。

代码

//
//  SPOJ SUBLEX.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/10.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#define MAXN 90005

struct SAM_State{
    int mxn;
    int cnt;
    int id;
    SAM_State *to[26];
    SAM_State *parent;
    void init(int _mxn){
        mxn = _mxn;
        memset(to, NULL, sizeof(to));
        parent = NULL;
        cnt = 0;
        id = 0;
    }
} idx[2*MAXN];

int totalNode = 0;
int len = 0;
SAM_State *idx_sorted[2*MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = &idx[++totalNode];
    np -> mxn = p -> mxn + 1;
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = &idx[++totalNode];
            *nq = *q;
            nq -> mxn = p -> mxn + 1;
            q -> parent = nq;
            np -> parent = nq;
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

void SAM_Init(int n){
    for (int i = 0; i <= n ; i++) {
        idx[i].init(0);
    }
    totalNode = 0;
}

SAM_State* SAM_Build(char* str){
    len = (int)strlen(str);
    SAM_Init(2*len);
    SAM_State *root = &idx[0];
    SAM_State *last = root;
    for (int i = 0; i < len; i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}

int cnt[MAXN*2];
void SAM_Toposort(){
    for (int i = 0; i <= totalNode; i++) {
        idx[i].id = i;
        cnt[idx[i].mxn]++;
    }
    for (int i = 1; i <= len; i++) {
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i <= totalNode; i++) {
        idx_sorted[--cnt[idx[i].mxn]] = &idx[i];
    }
}

int childID[MAXN*2][26];
int childVal[MAXN*2][26];
char childCh[MAXN*2][26];
int childCnt[MAXN*2];
void SAM_Buildgraph(){
    for (int i = totalNode; i >= 0; i--) {
        SAM_State *cur = idx_sorted[i];
        int curid = cur -> id;
        for (int j = 0; j < 26; j++) {
            if (cur -> to[j] != NULL) {
                SAM_State *nxt = cur -> to[j];
                int nxtid = nxt -> id;
                childID[curid][childCnt[curid]] = nxtid;
                childVal[curid][childCnt[curid]] = nxt -> cnt + 1;
                childCh[curid][childCnt[curid]] = j + 'a';
                cur -> cnt += nxt -> cnt + 1;
                childCnt[curid]++;
            }
        }
    }
}

char ans[MAXN];
void get_ans(int k){
    int pos = 0;
    SAM_State *cur = &idx[0];
    while (k) {
        for (int i = 0; i < childCnt[cur -> id]; i++) {
            if (childVal[cur -> id][i] < k) {
                k -= childVal[cur -> id][i];
            }else {
                k--;
                ans[pos] = childCh[cur -> id][i];
                cur = &idx[childID[cur -> id][i]];
                pos++;
                break;
            }
        }
    }
    ans[pos] = '\0';
    puts(ans);
}

char a[MAXN];
int main(){
    scanf(" %s",a);
    SAM_Build(a);
    SAM_Toposort();
    SAM_Buildgraph();
    int q = 0;
    scanf(" %d",&q);
    for (int i = 1; i <= q; i++) {
        int k = 0;
        scanf(" %d",&k);
        get_ans(k);
    }
    return 0;
}

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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

// SPOJ SUBLEX.cpp

// playground

// Created by Adam Chang on 2015/08/10.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#define MAXN 90005

struct SAM_State{

int mxn;

int cnt;

int id;

SAM_State *to[26];

SAM_State *parent;

void init(int _mxn){

mxn = _mxn;

memset(to, NULL, sizeof(to));

parent = NULL;

cnt = 0;

id = 0;

}

} idx[2*MAXN];

int totalNode = 0;

int len = 0;

SAM_State *idx_sorted[2*MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = &idx[++totalNode];

np -> mxn = p -> mxn + 1;

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = &idx[++totalNode];

*nq = *q;

nq -> mxn = p -> mxn + 1;

q -> parent = nq;

np -> parent = nq;

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

void SAM_Init(int n){

for (int i = 0; i <= n ; i++) {

idx[i].init(0);

}

totalNode = 0;

}

SAM_State* SAM_Build(char* str){

len = (int)strlen(str);

SAM_Init(2*len);

SAM_State *root = &idx[0];

SAM_State *last = root;

for (int i = 0; i < len; i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int cnt[MAXN*2];

void SAM_Toposort(){

for (int i = 0; i <= totalNode; i++) {

idx[i].id = i;

cnt[idx[i].mxn]++;

}

for (int i = 1; i <= len; i++) {

cnt[i] += cnt[i-1];

}

for (int i = 0; i <= totalNode; i++) {

idx_sorted[--cnt[idx[i].mxn]] = &idx[i];

}

int childID[MAXN*2][26];

int childVal[MAXN*2][26];

char childCh[MAXN*2][26];

int childCnt[MAXN*2];

void SAM_Buildgraph(){

for (int i = totalNode; i >= 0; i--) {

SAM_State *cur = idx_sorted[i];

int curid = cur -> id;

for (int j = 0; j < 26; j++) {

if (cur -> to[j] != NULL) {

SAM_State *nxt = cur -> to[j];

int nxtid = nxt -> id;

childID[curid][childCnt[curid]] = nxtid;

childVal[curid][childCnt[curid]] = nxt -> cnt + 1;

childCh[curid][childCnt[curid]] = j + 'a';

cur -> cnt += nxt -> cnt + 1;

childCnt[curid]++;

}

char ans[MAXN];

void get_ans(int k){

int pos = 0;

SAM_State *cur = &idx[0];

while (k) {

for (int i = 0; i < childCnt[cur -> id]; i++) {

if (childVal[cur -> id][i] < k) {

k -= childVal[cur -> id][i];

}else {

k--;

ans[pos] = childCh[cur -> id][i];

cur = &idx[childID[cur -> id][i]];

pos++;

break;

}

ans[pos] = '\0';

puts(ans);

}

char a[MAXN];

int main(){

scanf(" %s",a);

SAM_Build(a);

SAM_Toposort();

SAM_Buildgraph();

int q = 0;

scanf(" %d",&q);

for (int i = 1; i <= q; i++) {

int k = 0;

scanf(" %d",&k);

get_ans(k);

}

return 0;

}

SPOJ LCS Longest Common Substring

August 09, 20152015-08-09hahaschool2 Comments

［等待填坑］

//
//  SPOJ LCS.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/08.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct SAM_State{
    int mxn;
    SAM_State *to[26];
    SAM_State *parent;
    SAM_State(int _mxn){
        mxn = _mxn;
        memset(to, 0, sizeof(to));
        parent = NULL;
    }
};

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = new SAM_State(p -> mxn + 1);
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            nq -> parent = q -> parent;
            q -> parent = nq;
            np -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

SAM_State* SAM_Build(string str){
    SAM_State *root = new SAM_State(0);
    SAM_State *last = root;
    for (int i = 0; i < str.size(); i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}


int main(){
    string a,b;
    cin >> a >> b;
    SAM_State *sam_root = SAM_Build(a);
    SAM_State *sam = sam_root;
    int ans = 0;
    int curcnt = 0;
    for (int i = 0; i < b.size(); i++) {
        if (sam -> to[b[i]-'a'] != NULL) {
            curcnt++;
            sam = sam -> to[b[i]-'a'];
        }else{
            ans = max(curcnt,ans);
            curcnt = 0;
            while (sam -> parent) {
                sam = sam -> parent;
                if (sam -> to[b[i]-'a'] != NULL) {
                    curcnt = sam->mxn+1;
                    sam = sam -> to[b[i]-'a'];
                    break;
                }
            }
        }
    }
    cout << max(curcnt,ans) << endl;
    return 0;
}

100

101

102

103

// SPOJ LCS.cpp

// playground

// Created by Adam Chang on 2015/08/08.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct SAM_State{

int mxn;

SAM_State *to[26];

SAM_State *parent;

SAM_State(int _mxn){

mxn = _mxn;

memset(to, 0, sizeof(to));

parent = NULL;

}

};

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = new SAM_State(p -> mxn + 1);

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = new SAM_State(p -> mxn + 1);

nq -> parent = q -> parent;

q -> parent = nq;

np -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

SAM_State* SAM_Build(string str){

SAM_State *root = new SAM_State(0);

SAM_State *last = root;

for (int i = 0; i < str.size(); i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int main(){

string a,b;

cin >> a >> b;

SAM_State *sam_root = SAM_Build(a);

SAM_State *sam = sam_root;

int ans = 0;

int curcnt = 0;

for (int i = 0; i < b.size(); i++) {

if (sam -> to[b[i]-'a'] != NULL) {

curcnt++;

sam = sam -> to[b[i]-'a'];

}else{

ans = max(curcnt,ans);

curcnt = 0;

while (sam -> parent) {

sam = sam -> parent;

if (sam -> to[b[i]-'a'] != NULL) {

curcnt = sam->mxn+1;

sam = sam -> to[b[i]-'a'];

break;

}

cout << max(curcnt,ans) << endl;

return 0;

}

SPOJ LCS2 Longest Common Substring II

August 09, 20152015-08-09hahaschoolLeave a comment

［详细题解等待填坑］

SPOJ真是业界奇葩

//
//  SPOJ LCS2.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/08.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct SAM_State{
    int mxn;
    int mi;
    int mx;
    SAM_State *to[26];
    SAM_State *parent;
    void init(int _mxn){
        mxn = _mxn;
        memset(to, NULL, sizeof(to));
        parent = NULL;
        mx = 0;
        mi = 909303;
    }
} idx[200005];

int totalNode = 0;
int mxmxn = 0;
SAM_State *idx_sorted[200005];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = &idx[++totalNode];
    np -> mxn = p -> mxn + 1;
    mxmxn = max(mxmxn, np -> mxn);
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = &idx[++totalNode];
            *nq = *q;
            nq -> mxn = p -> mxn + 1;
            q -> parent = nq;
            np -> parent = nq;
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

void init(int n){
    for (int i = 0; i <= n ; i++) {
        idx[i].init(0);
    }
    totalNode = 0;
    mxmxn = 0;
}

SAM_State* SAM_Build(char* str){
    int len = (int)strlen(str);
    init(2*len);
    SAM_State *root = &idx[0];
    SAM_State *last = root;
    for (int i = 0; i < len; i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}

int cnt[100005];
void toposort(){
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= totalNode; i++) {
        cnt[idx[i].mxn]++;
    }
    for (int i = 1; i <= mxmxn; i++) {
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i <= totalNode; i++) {
        idx_sorted[--cnt[idx[i].mxn]] = &idx[i];
    }
}



char a[100005];

int main(){
    scanf("%s",a);
    SAM_State *sam_root = SAM_Build(a);
    toposort();
    while (scanf("%s",a) != EOF) {
        int len = (int)strlen(a);
        SAM_State *sam = sam_root;
        int tmp = 0;
        for (int i = 0; i < len; i++) {
            if (sam -> to[a[i] - 'a'] != NULL) {
                tmp++;
                sam = sam -> to[a[i] - 'a'];
            }else{
                while (sam && sam -> to[a[i] - 'a'] == NULL) {
                    sam = sam -> parent;
                }
                if (sam == NULL) {
                    sam = sam_root;
                    tmp = 0;
                }else{
                    tmp = sam -> mxn + 1;
                    sam = sam -> to[a[i] - 'a'];
                }
            }
            sam -> mx = max(sam -> mx, tmp);
        }
        for (int j = totalNode; j >= 0; j--) {
            SAM_State *cur = idx_sorted[j];
            cur -> mi = min(cur -> mi, cur -> mx);
            if (cur -> parent != NULL) {
                cur -> parent -> mx = max(cur -> parent -> mx, cur -> mx);
                cur -> parent -> mx = min(cur -> parent -> mxn,cur -> parent -> mx);
            }
            cur -> mx = 0;
        }
    }
    int res = 0;
    for (int i = 0; i <= totalNode; i++) {
        res = max(idx[i].mi, res);
    }
    printf("%d\n",res);
    return 0;
}

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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

// SPOJ LCS2.cpp

// playground

// Created by Adam Chang on 2015/08/08.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct SAM_State{

int mxn;

int mi;

int mx;

SAM_State *to[26];

SAM_State *parent;

void init(int _mxn){

mxn = _mxn;

memset(to, NULL, sizeof(to));

parent = NULL;

mx = 0;

mi = 909303;

}

} idx[200005];

int totalNode = 0;

int mxmxn = 0;

SAM_State *idx_sorted[200005];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = &idx[++totalNode];

np -> mxn = p -> mxn + 1;

mxmxn = max(mxmxn, np -> mxn);

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = &idx[++totalNode];

*nq = *q;

nq -> mxn = p -> mxn + 1;

q -> parent = nq;

np -> parent = nq;

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

void init(int n){

for (int i = 0; i <= n ; i++) {

idx[i].init(0);

}

totalNode = 0;

mxmxn = 0;

}

SAM_State* SAM_Build(char* str){

int len = (int)strlen(str);

init(2*len);

SAM_State *root = &idx[0];

SAM_State *last = root;

for (int i = 0; i < len; i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int cnt[100005];

void toposort(){

memset(cnt, 0, sizeof(cnt));

for (int i = 0; i <= totalNode; i++) {

cnt[idx[i].mxn]++;

}

for (int i = 1; i <= mxmxn; i++) {

cnt[i] += cnt[i-1];

}

for (int i = 0; i <= totalNode; i++) {

idx_sorted[--cnt[idx[i].mxn]] = &idx[i];

}

char a[100005];

int main(){

scanf("%s",a);

SAM_State *sam_root = SAM_Build(a);

toposort();

while (scanf("%s",a) != EOF) {

int len = (int)strlen(a);

SAM_State *sam = sam_root;

int tmp = 0;

for (int i = 0; i < len; i++) {

if (sam -> to[a[i] - 'a'] != NULL) {

tmp++;

sam = sam -> to[a[i] - 'a'];

}else{

while (sam && sam -> to[a[i] - 'a'] == NULL) {

sam = sam -> parent;

}

if (sam == NULL) {

sam = sam_root;

tmp = 0;

}else{

tmp = sam -> mxn + 1;

sam = sam -> to[a[i] - 'a'];

}

sam -> mx = max(sam -> mx, tmp);

}

for (int j = totalNode; j >= 0; j--) {

SAM_State *cur = idx_sorted[j];

cur -> mi = min(cur -> mi, cur -> mx);

if (cur -> parent != NULL) {

cur -> parent -> mx = max(cur -> parent -> mx, cur -> mx);

cur -> parent -> mx = min(cur -> parent -> mxn,cur -> parent -> mx);

}

cur -> mx = 0;

}

int res = 0;

for (int i = 0; i <= totalNode; i++) {

res = max(idx[i].mi, res);

}

printf("%d\n",res);

return 0;

}

SPOJ SORTBIT Sorted bit squence

August 05, 20152015-08-05hahaschoolLeave a comment

［等待填坑］

//
//  SPOJ SORTBIT.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/04.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

unsigned int cnt[33][33];//cnt[height][required num of 1]
void get_cnt(){
    cnt[0][0] = 1;
    cnt[1][0] = 1;
    cnt[1][1] = 1;
    for (int i = 2; i <= 32; i++) {
        cnt[i][0] = 1;
        for (int j = 1; j <= 32; j++) {
            cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];
        }
    }
}

unsigned int count_to(unsigned int a, int k){
    unsigned int ret = 0;
    int hav = 0;
    for (int i = 31; i >= 0; i--) {
        if (a & (1U << (unsigned int)i)) {
            if (k >= hav) {
                ret += cnt[i][k - hav];
            }
            hav++;
        }
    }
    return ret;
}

unsigned int count_num(int lb, int rb, int k){
    unsigned int ret = 0;
    if (lb > rb) {
        swap(lb, rb);
    }
    unsigned int ulb = lb, urb = rb;
    if (lb * rb != 0) {
        if (lb > 0) {
            ret = count_to(urb+1,k) - count_to(ulb, k);
        }else {
            if (rb == -1) {
                ret = count_to(urb, k) - count_to(ulb, k);
                if (k == 32) {
                    ret++;
                }
            }else{
                ret = count_to(urb+1, k) - count_to(ulb, k);
            }
        }
    }else {
        if (lb == 0) {
            ret = count_to(urb+1, k);
        }else {
            ret = cnt[32][k] - count_to(ulb, k);
            if (k == 0) {
                ret++;
            }
        }
    }
    return ret;
}

int get_ans(int m, int n, long long k){
    if (m > n) {
        swap(m, n);
    }
    long long curcnt = 0;
    long long target = 0;
    int lasti = 0;
    for (int i = 0; i <= 32; i++) {
        lasti = i;
        curcnt += count_num(m, n, i);
        if (curcnt >= k) {
            target = count_num(m, n, i) - curcnt + k;
            break;
        }
    }
    int l = m, r = n, mid = l + (r - l)/2;
    while (l < r) {
        if (count_num(m, mid, lasti) < target) {
            l = mid + 1;
        }else {
            r = mid;
        }
        mid = l + (r - l)/2;
    }
    return mid;
}

int main(){
    get_cnt();
    int caseCnt = 0;
    cin >> caseCnt;
    while (caseCnt--) {
        int m = 0, n = 0, k = 0;
        cin >> m >> n >> k;
        cout << get_ans(m, n, k) << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// SPOJ SORTBIT.cpp

// playground

// Created by Adam Chang on 2015/08/04.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

unsigned int cnt[33][33];//cnt[height][required num of 1]

void get_cnt(){

cnt[0][0] = 1;

cnt[1][0] = 1;

cnt[1][1] = 1;

for (int i = 2; i <= 32; i++) {

cnt[i][0] = 1;

for (int j = 1; j <= 32; j++) {

cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];

}

unsigned int count_to(unsigned int a, int k){

unsigned int ret = 0;

int hav = 0;

for (int i = 31; i >= 0; i--) {

if (a & (1U << (unsigned int)i)) {

if (k >= hav) {

ret += cnt[i][k - hav];

}

hav++;

}

return ret;

}

unsigned int count_num(int lb, int rb, int k){

unsigned int ret = 0;

if (lb > rb) {

swap(lb, rb);

}

unsigned int ulb = lb, urb = rb;

if (lb * rb != 0) {

if (lb > 0) {

ret = count_to(urb+1,k) - count_to(ulb, k);

}else {

if (rb == -1) {

ret = count_to(urb, k) - count_to(ulb, k);

if (k == 32) {

ret++;

}

}else{

ret = count_to(urb+1, k) - count_to(ulb, k);

}

}else {

if (lb == 0) {

ret = count_to(urb+1, k);

}else {

ret = cnt[32][k] - count_to(ulb, k);

if (k == 0) {

ret++;

}

return ret;

}

int get_ans(int m, int n, long long k){

if (m > n) {

swap(m, n);

}

long long curcnt = 0;

long long target = 0;

int lasti = 0;

for (int i = 0; i <= 32; i++) {

lasti = i;

curcnt += count_num(m, n, i);

if (curcnt >= k) {

target = count_num(m, n, i) - curcnt + k;

break;

}

int l = m, r = n, mid = l + (r - l)/2;

while (l < r) {

if (count_num(m, mid, lasti) < target) {

l = mid + 1;

}else {

r = mid;

}

mid = l + (r - l)/2;

}

return mid;

}

int main(){

get_cnt();

int caseCnt = 0;

cin >> caseCnt;

while (caseCnt--) {

int m = 0, n = 0, k = 0;

cin >> m >> n >> k;

cout << get_ans(m, n, k) << endl;

}

return 0;

}