【NOI五连测】[D3T2] 加密

Qizy Suffix Array, Suffix Automaton, 字符串, 解题报告

题目传送门：http://pan.baidu.com/s/1qYPBdpU
数据生成器：http://paste.ubuntu.com/19351549/
OJ传送门：http://oi.cdshishi.net:8080/Problem/1719

这道题目，一看，SA的板题嘛！于是很高兴的码了SA
码完之后一对拍，发现，好像常数很大的样子，然而一看数据范围，嗯，一定是O(nlogn)的复杂度
结果，又被卡常了QAQ

说一说SA的做法：
首先在SA上二分，搞出len
然后再次在SA上二分，搞出最小的标号
然后总体复杂度O(6*n*log(n))，于是T了一个点QAQ

再来说一说SAM的做法（QJC说：这不是SAM的一眼题吗QAQ）
两个字串的lcp，是fail树上的lca，于是考虑在lca上染色的话，O(n)即可
另外，此题不是要求的不是后缀关系，是前缀关系，于是我们倒着建即可

SA版本：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000000+9;
const int SGZ = 26;
const int INF = 100000000;

char pat[MAXN];
int n;

namespace Suffix_Array{
	#define SA Suffix_Array
	int height[MAXN],sa[MAXN],t1[MAXN],t2[MAXN],bot[MAXN];
	int *tmp,*rank,m,K[MAXN],LEN[MAXN];
	
	inline void ST_Advance(){
		for (int i=1,k,len;i<=n;i++) {
			k = 0, len = 1;
			while (len < i) len *= 2, k++;
			K[i] = k; LEN[i] = len;
		}
	}
	
	struct Sparse_Table{
		int MN[MAXN][20];
		
		inline void init(int *arr){
			for (int i=1;i<=n;i++) MN[i][0] = arr[i];
			for (int k=1,lim=2;k<=19;k++,lim=1<<k) for (int i=1;i<=n-lim+1;i++)
				MN[i][k] = min(MN[i][k-1], MN[i+(1<<(k-1))][k-1]);
		}
		
		inline int query(int a, int b){
			if (a > b) swap(a, b); 
			int sta=(b-a+2)/2,k=K[sta],len=LEN[sta];
			return min(MN[a][k], MN[b-len+1][k]);
		}
	}ST_num,ST_hei;
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) if (rank[i] > 1) {
			int sta = max(0, height[rank[i-1]]-1);
			int p1 = sta + i, p2 = sta + sa[rank[i]-1];
			while (pat[p1++] == pat[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		tmp = t1, rank = t2;
		n = strlen(pat+1); m = SGZ;
		for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+1]++;
		for (int i=2;i<=m;i++) bot[i] += bot[i-1];
		for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++) 
			if (tmp[sa[i]] != tmp[sa[i-1]]) rank[sa[i]] = ++m;
			else rank[sa[i]] = m;
		
		for (int k=1;k<=n;k*=2) { int T = 0;
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--]  = tmp[i];
			
			swap(tmp, rank); rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++) 
				if (tmp[sa[i]] != tmp[sa[i-1]] || tmp[sa[i]+k] != tmp[sa[i-1]+k]) rank[sa[i]] = ++m;
				else rank[sa[i]] = m; 
			
			if (m >= n) break;
		}
		GetHeight();
		ST_Advance();
		ST_num.init(sa);
		ST_hei.init(height);
	}
	
	inline void solve(){
		for (int w=1,tag=0;w<n;tag=0) {
			int mid, l = 1, r = rank[w] - 1, len = 0, ans = 0;
			while (l <= r) {
				mid = (l + r) / 2;
				if (ST_num.query(rank[w]-mid,rank[w]-1) < w) r = mid-1, len = mid;
				else l = mid+1;
			}
			if (len) ans = ST_hei.query(rank[w]-len+1, rank[w]);
			
			l = 1; r = n - rank[w]; len = 0;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (ST_num.query(rank[w]+1, rank[w]+mid) < w) r = mid-1, len = mid;
				else l = mid+1; 
			} 
			if (len) ans = max(ans, ST_hei.query(rank[w]+1, rank[w]+len));
			
			if (ans) {
				printf("%d ",ans); tag = ans;
				l = 1; r = rank[w]; len = 0; ans = INF;
				while (l <= r) {
					mid = (l + r) / 2;
					if (ST_hei.query(rank[w], rank[w]-mid+1) >= tag) l = mid+1, len = mid;
					else r = mid-1; 
				} 
				if (len) ans = ST_num.query(rank[w]-len,rank[w]-1);
				l = 1; r = n-rank[w]; len = 0;
				while (l <= r) {
					mid = (l + r) / 2;
					if (ST_hei.query(rank[w]+1, rank[w] + mid) >= tag) l = mid+1, len = mid;
					else r = mid-1;			
				}
				if (len) ans = min(ans, ST_num.query(rank[w]+1, rank[w]+len));
				printf("%d ",ans-1); w += tag;
			} else {
				printf("%d %d ",-1,(int)pat[w]);
				w ++;
			}
		}
	}
};

int main(){
	freopen("encrypt.in","r",stdin);
	freopen("encrypt.out","w",stdout);
	scanf("%s",pat+1);
	SA::build();
	SA::solve();
	return 0;
}

SAM版本：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000000+9;
const int SGZ = 27;

char pat[MAXN];
int n;

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int ch[MAXN][SGZ],fail[MAXN],tag[MAXN],W=1;
	int cnt,last,dep[MAXN],pos[MAXN];
	
	inline void extend(int i, int c){
		int w = last; dep[pos[i]=last=++cnt] = dep[w]+1; 
		while (w && !ch[w]) ch[w] = last, w = fail[w];
		if (!ch[w]) fail[last] = 1;
		else {
			int nw = ch[w];
			if (dep[nw] == dep[w] + 1) fail[last] = nw;
			else {
				int nnw = ++cnt; dep[nnw] = dep[w] + 1;
				memcpy(ch[nnw],ch[nw],sizeof(ch[nw]));
				fail[nnw] = fail[nw]; fail[nw] = fail[last] = nnw;
				while (ch[w] == nw) ch[w] = nnw, w = fail[w];
			}
		}
	}
	
	inline void sign(int w, int val) {
		while (w && !tag[w]) 
			tag[w] = val, w = fail[w];
		if (W == val) {
			if (w <= 1) printf("-1 %d ",(int)pat[val]), W++;
			else printf("%d %d ",dep[w],tag[w]-1), W += dep[w]; 
		}
	}
	
	inline void build(char *s){
		n = strlen(s+1); cnt = last = 1;
		for (int i=n;i;i--) extend(i, pat[i]-'a'+1);
		for (int i=1;i<=n;i++) sign(pos[i], i);
	}
};

int main(){
	scanf("%s",pat+1);
	SAM::build(pat);
	return 0;
}

看看SA将近4k的代码
再看看SAM只有1.2k的代码
SA，你还要我怎么爱你QAQ

167 thoughts to “【NOI五连测】[D3T2] 加密”

  17. With havin so much content and articles do you ever run into
    any issues of plagorism or copyright violation? My website
    has a lot of completely unique content I’ve either written myself or outsourced but
    it looks like a lot of it is popping it up all over the
    internet without my authorization. Do you know any
    methods to help protect against content from being ripped off?

    I’d really appreciate it.

    Reply

  21. Howdy! I’m at work browsing your blog from my new apple iphone!
    Just wanted to say I love reading through
    your blog and look forward to all your posts! Carry on the
    superb work!

    Reply

  22. I’m not that much of a internet reader to be honest but
    your blogs really nice, keep it up! I’ll go ahead and bookmark your website to come back later.
    All the best

    Reply

  30. Hi there would you mind letting me know which web host you’re utilizing?
    I’ve loaded your blog in 3 different web browsers and I must say this blog loads a lot faster then most.
    Can you suggest a good internet hosting provider at a reasonable price?
    Kudos, I appreciate it!

    Reply

  39. I want to to thank you for this excellent read!! I definitely enjoyed every bit of it.
    I have got you bookmarked to check out new stuff
    you post…

    Reply

  47. Greetings from Ohio! I’m bored at work so I decided to
    browse your website on my iphone during lunch break.

    I enjoy the information you provide here and can’t wait to take a look when I get home.
    I’m shocked at how fast your blog loaded on my phone ..
    I’m not even using WIFI, just 3G .. Anyways,
    wonderful site!

    Reply

  51. Its like you read my thoughts! You appear to know a lot approximately this, like you wrote the e
    book in it or something. I think that you simply can do with some p.c.
    to force the message house a bit, but instead of that, this is excellent
    blog. A fantastic read. I’ll certainly be back.

    Reply

  54. I like what you guys are up too. Such clever work and reporting! Keep up the excellent works guys I¦ve incorporated you guys to my blogroll. I think it’ll improve the value of my web site 🙂

    Reply

  67. I was wondering if you ever considered changing the page layout of your blog?
    Its very well written; I love what youve got to say.

    But maybe you could a little more in the way of content so
    people could connect with it better. Youve got an awful lot of text
    for only having 1 or 2 images. Maybe you could space it out
    better?

    Reply

  82. Hi there! I know this is kinda off topic however I’d figured I’d
    ask. Would you be interested in exchanging links or maybe guest writing a blog article or vice-versa?
    My blog discusses a lot of the same subjects as yours and I feel we could
    greatly benefit from each other. If you might be interested feel free to shoot me an e-mail.
    I look forward to hearing from you! Great blog by the way!

    Reply

  91. Unquestionably imagine that that you stated.
    Your favourite justification appeared to be at the internet the easiest thing to be mindful of.
    I say to you, I definitely get irked whilst people consider worries that they plainly do not recognise about.
    You controlled to hit the nail upon the highest and defined out the entire thing
    without having side-effects , people can take a
    signal. Will likely be again to get more. Thank you

    Reply

  129. I’ve been absent for a while, but now I remember why I used to love this website. Thank you, I will try and check back more often. How frequently you update your site?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *