代码

poj2774:对后缀数组的复仇,O(nlog n)做法

话说上次发了一篇文章..A掉了2774这道水题,但是!用的是O(nlog^2 n)做法,有些不服..

于是本人又研究了一次后缀数组的O(nlog n)做法,终于在昨晚领悟了!特A一题..终于可以教会师弟师妹们这一种数据结构了..哭

直接上代码吧..

Source Code
/*
Problem: 2774		User: aclolicon
Memory: 5212K		Time: 610MS
Language: G++		Result: Accepted
Source Code*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 200500
using namespace std;
char s[MAXN], s2[MAXN];
int n, len;
int sa[MAXN], c[MAXN], t[MAXN], t2[MAXN], rank[MAXN], height[MAXN];
void buildsa(){
	int *x = t, *y = t2, m = 300;
	memset(c, 0, sizeof(c));

	for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
	for (int i = 1; i < m; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
	for (int k = 1; k <= n; k *= 2){
		int p = 0;
		for (int i = n - k; i < n; i++) y[p++] = i;
		for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
		memset(c, 0, sizeof(c));
		for (int i = 0; i < n; i++) c[x[y[i]]]++;
		for (int i = 1; i < m; i++) c[i] += c[i - 1];
		for (int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] =y[i];
		swap(x, y);
		p = 1;
		x[sa[0]] = 0;
		for (int i = 1; i < n; i++) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])? p - 1: p++;
		if (p >= n) break;
		m = p;
	}
} 

void geth(){
	n = strlen(s);
	for (int i = 0; i <= n; i++) rank[sa[i]] = i;
	int h = 0;
	height[0] = 0;
	for (int i = 0; i < n; i++){
		int j = sa[rank[i] - 1];
		if (h > 0) h--;
		for (; j + h < n && i + h < n; h++){
			if (s[j + h] != s[i + h]) break;
		}
		height[rank[i] - 1] = h;
	}
}
int main(){
	while(scanf("%s", s) > 0){
		scanf("%s", s2) > 0;
		len = strlen(s2);
		n = strlen(s);
		if (s2 > s) swap(s, s2);
		s[len] = '$';
		for (int i = len + 1; i < len + n + 1; i++) s[i] = s2[i - len - 1];
		n = strlen(s) + 1;
		buildsa();
		geth();
		int maxh = -1;
		for (int i = 0; i < n; i++){
			if((sa[i] < len) != (sa[i + 1] < len)){
				maxh = max(maxh, height[i]);
			}
		}
		printf("%d", maxh);
	}
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

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

相关推荐