[HDOJ 4436 a.k.a 天津2012 F] 后缀自动机

【题意】

给定N个数字串,每个串的子串成一个数字,问这些数字放进一个set里面去重后和模2012是多少

【算法】
后缀数组也可以做,但是后缀自动机无疑简单一点。
类似于后缀数组,把所有串通过10这个不属于任意一个数字的元素串连在一起。
然后把结点按val直接sort一下,从前往后递推统计。
递推的时候记录两个值,到达这个结点的方案数way以及到达这个状态的数字之和sum。
每次接收一个c转移显然就应该是给下一个结点的sum加上$$\sum_{i = 1}^{way} (number_i * 10 + c)$$。
把这个式子的常数c拉出来就是$$way * c + 10 * \sum_{i = 1}^{way} number_i$$
亦即$$way * c + 10 * sum$$
就这样从前往后推一下就好了,最后把每个结点的sum值都加起来就是答案。
推的时候要注意的就只有两点

  1. 根节点不应该接收0开头的串,因为这会弄出有前导0的串从而导致重复,这个很显然吧。
  2. 所有的转移都无视10这个分支,因为那本身就是不应该走的…这个也很显然把。

【时间复杂度】
$$O(N * 11 + N \log N)$$
其中N为输入字符总数。后面的N lg N是因为我贪方便直接按val sort了,这一步用了链表跳一下很容易做到O(n)的。 11自然就是字符集大小了。
【空间复杂度】
$$O(N * 11)$$
【吐槽】
今天贴了后缀自动机的模板以后花了不到5分钟就过掉了…现场调了1小时没过是怎么回事,当时的做法是一模一样的 :Cry-Out: 难道又是模板敲错了?
好后悔没有把现场打印的代码拿回来。

#include 
#include 
#include 
#include 
#include 
using namespace std;

template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 250005;
const int Mod = 2012;

struct Node {
	Node *ch[11], *fa;
	int val;
	int way;
	int sum;
	Node(): 
		val(0), fa(NULL), way(0), sum(0) { 
		memset(ch, 0, sizeof(ch));
	}
}pool[N * 2 + 5], *last, *root;
vector  vec[N];

namespace SAM {
	int cnt;

	void init() {
		if (cnt)
			for (int i = 0; i < cnt; i++)
				pool[i] = Node();
		cnt = 1;
		root = &pool[0];
		last = root;
	}

	void add(int c) {
		Node *p = last, *np = &pool[cnt++];
		last = np;
		np->val = p->val + 1;
		for  (; p && !p->ch; p = p->fa)
			p->ch = np;
		if (!p) {
			np->fa = root;
		} else {
			Node *q = p->ch;
			if (p->val + 1 == q->val) {
				 np->fa = q;
			} else {
				Node *nq = &pool[cnt++];
				*nq = *q;
				nq->val = p->val + 1;
				q->fa = nq;
				np->fa = nq;
				for (; p && p->ch == q; p = p->fa)
					p->ch = nq;
			}
		}
	}
}

bool cmp(int i, int j) {
	return pool[i].val < pool[j].val;
}

int n, m;
char S[N], buf[N];

void calc() {
	int ans = 0;
	vector  vec;
	for (int i = 0; i < SAM::cnt; i++) {
		vec.push_back(i);
		pool[i].way = pool[i].sum = 0;
	}
	sort(vec.begin(), vec.end(), cmp);
	root->way = 1;
	root->sum = 0;
	foreach (it, vec) {
		int i = *it;
		Node *p = &pool[i];
		for (int c = i == 0 ? 1 : 0; c < 10; c++) {
			if (p->ch) {
				p->ch->way += p->way;
				p->ch->way %= Mod;
				p->ch->sum += p->sum * 10 + p->way * c;
				p->ch->sum %= Mod;
			}
		}
		ans += p->sum;
		ans %= Mod;
	}
	printf("%d\n", ans);
}

int main(){
	while (scanf("%d", &n) != EOF) {
		m = 0;
		SAM::init();
		for (int i = 0; i < n; i++) {
			scanf("%s", buf);
			int len = strlen(buf);
			for (int j = 0; j < len; j++) {
				SAM::add(buf[j] - '0');
			}
			SAM::add(10);
		}
		calc();
	}
}

[ZOJ3199 Longest Repeated Substring]【后缀数组】【枚举答案】

【题目链接】http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3324

【题目大意】

给定一个串,让你求里面的最长连续重复子串的长度。

这个连续重复子串是这么定义的:

设S为原串Str里的一个子串,如果在Str里,S后面紧接着一个和S一模一样的串,那么S被称为连续重复子串。

【算法分析】

枚举答案ans,对原串的n/ans个字符进行标记,每个字符之间间隔ans-1个字符。

那么假如答案ans成立,那么对应长度为ans的连续重复子串必然包含且仅包含一个被标记的字符。

然后他紧接着和他一模一样的字符串必然会包含且仅包含下一个被标记的字符。

于是令现在其中一个标记为i,我们只需要求(i,i+ans)之间的最长公共前缀和最长公共后缀就可以了。

最长公共前缀和最长公共后缀可以通过建立一个正向字符串的后缀数组和一个逆向字符串的后缀数组来实现。

【时间复杂度】O(n lg n)  【n/1+n/2+n/3+…+n/n <= n lg n】

【空间复杂度】O(n lg n)

【CODE】http://xiudaima.appspot.com/code/detail/4293043

[HDOJ3553 Just a String]【后缀数组搞的像Treap一样的伪后缀树】★★

【题目大意】
一个串的子串定义为其中连续的某一段。
给定一个串,问他的所有子串中,字典序为m的是哪一个子串?
【算法分析】
这个是典型的后缀树问题。只需深度优先遍历一下后缀树就很容易得到这个解。
现在问题来了。。。我不会O(n)构造后缀树。
好吧。那么退一步,我搞个后缀数组。
然后把height建好。然后可以发现。。。其实我们可以在这个搞好的后缀树上模拟后缀树的DFS遍历。。。
好吧,说说这种从Suffix Array->Suffix Tree的沙茶做法。
考虑现在我们已经建好height的ST表,那么我们每次取一个height最小的地方,按这个点划分成两半。然后两半在各自划分下去。
然后现在搞成了一棵heap的关键字是 height ,平衡树的关键字是 某后缀 的“Treap”。
好了。。我们现在可以在这颗“伪后缀树”上搞了。
显然,如果是真的后缀树的话,我们的做法应当是从小到大判断每个叉加起来的子串数量够不够m。然后每次只需选一个叉前进即可。
当然,有可能不前进,那就是后缀树的这个点所压缩的东西,已经足够m了。
然后现在我们来看看这颗伪后缀树和真后缀树的差别。
其实他们所不同的地方就是,假如当前节点有2个以上分叉,
那么后缀树会搞出相等数量的分叉在弄下去。
而对于现在这颗伪后缀树,我们会选择任意一个叉,然后再将它们划分成两边。
然后这样就会造成本身是同深度的叉,变成深度不同了。其实将这些叉合回来就是真后缀树了。
但是对这个题目,我们并不需要把他合回来。现在的信息已经足够我们执行上面红色的算法了。
具体就是搞一个Len_Sum[i]表示后缀数组中前i个后缀的总长度。然后就可以O(1)判断那个叉是对的。然后跑下去。并用cut这个变量表示已经算好了ans的多少长度。
最后有一些琐碎的问题,就是那个后缀树的压缩连续的冗余结点,在这个伪后缀树里体现为假设每次取的那个height最小值!=cut的情况。这时这个伪后缀树中,height最小值-cut,就是那个压缩值的长度。
【其它】2Y。T_T。那个计算要用int64。读入也要。
【CODE】
#include #include #include #include #include using namespace std;
typedef long long lld;
const int N=105555;
int n;
lld m;
char S[N];
char ans[N];
int sa[N];
int lg[N];
int Sum[N];
int rank[N];
int List[N];
int a[N][3];
int b[N][3];
int height[N];
int rmq[18][N];
int pos[18][N];
lld Len_Sum[N];

bool cmp(int i,int j){return S[i]

void Radix_sort(){
     int i,k;
     for (k=1;k>=0;k–){
         for (i=0;i<=n;i++) Sum[i]=0;
         for (i=1;i<=n;i++) Sum[a[i][k]+1]++;
         for (i=1;i<=n;i++) Sum[i]+=Sum[i-1];
         for (i=1;i<=n;i++) memcpy(b[++Sum[a[i][k]]],a[i],12);
         for (i=1;i<=n;i++) memcpy(a[i],b[i],12);
     }
}

void make_suffix_arr(){
     int i,cnt,k,s;
     for (i=1;i<=n;i++) List[i]=i;
     sort(List+1,List+n+1,cmp);
     for (cnt=0,i=1;i<=n;i++)
       rank[List[i]]=( cnt+=(i==1 || S[List[i]]!=S[List[i-1]]) );
     for (k=1;cnt!=n;k++){
         s=1<<(k-1);
         for (i=1;i<=n;i++){
             a[i][0]=rank[i];
             a[i][1]=(i+s>n)?0:rank[i+s];
             a[i][2]=i;
         }
         Radix_sort();
         for (cnt=0,i=1;i<=n;i++)
           rank[a[i][2]]=( cnt+=(i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) );
     }
     for (i=1;i<=n;i++) sa[rank[i]]=i;
}

void make_height(){
     memset(height,0,sizeof(height));
     int i,j,k,st;
     for (i=1;i<=n;i++){
         if (rank[i]==1) continue;
         st=max(0,height[rank[i-1]]-1);
         j=i+st; k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && S[j]==S[k]){j++; k++; st++;}
         height[rank[i]]=st;
     }
}

void build_rmq(){
     int i,k;
     for (i=1;i<=n;i++){
         rmq[0][i]=height[i];
         pos[0][i]=i;
     }
     for (k=1;1<       for (i=1;i+(1<         if (rmq[k-1][i]<=rmq[k-1][i+(1<           rmq[k][i]=rmq[k-1][i];
           pos[k][i]=pos[k-1][i];
         }
         else{
           rmq[k][i]=rmq[k-1][i+(1<           pos[k][i]=pos[k-1][i+(1<         }
}

int Get_Min_Pos(int l,int r){
    if (l>r) swap(l,r);
    int k=lg[r-l+1];
    return rmq[k][l]<=rmq[k][r-(1<}

void Output(int i,int Len){
     int j;
     for (j=0;j       putchar(S[sa[i]+j]);
     putchar(‘n’);
}

void solve(){
     lld cnt=0,cut=0,l=1,r=n,i,res;
     Len_Sum[0]=0;
     for (i=1;i<=n;i++)
       Len_Sum[i]=Len_Sum[i-1]+(n-sa[i]+1);
     while (l           i=Get_Min_Pos(l+1,r);
           res=height[i]-cut;
           if (cnt+res*(r-l+1)>=m){
             Output(l,(m-cnt-1)/(r-l+1)+1+cut);
             return;
           }
           cnt+=res*(r-l+1);
           cut+=res;
           if (Len_Sum[i-1]-Len_Sum[l-1]-(i-l)*cut+cnt>=m)
             r=i-1;
           else{
             cnt+=Len_Sum[i-1]-Len_Sum[l-1]-(i-l)*cut;
             l=i;
           }
     }
     Output(l,m-cnt+cut);
}

int main(){
    int Tc,i;
    lg[1]=0;
    for (i=2;i      if (i==1<                      else lg[i]=lg[i-1];
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        scanf("%s %I64d",S+1,&m);
        printf("Case %d: ",i);
        n=strlen(S+1);
        make_suffix_arr();
        make_height();
        build_rmq();
        solve();
    }
}

[FZU1540 迎接光棍节]枚举+KMP Or 二分+后缀数组

【题目】多串的最长等差连续子串。中文题目:http://acm.fzu.edu.cn/problem.php?pid=1540

【算法分析】

这个作为后缀数组的经典例题之一。。。就不用说了。。。

但是很囧的是,我写的后缀数组MLE了= =。由于我的后缀数组特别搓,所以套模板的人们应该都可以过。

注意到这题的特殊性,n<=4000,每个串长<=200。

所以可以有一个暴力解法。

先等差处理。(a[i]-a[i-1])

然后枚举答案在串1中开始的位置。

于是以第一个串从枚举的开始位置到第一个串末端作为模式串。

去和n-1个串暴力KMP匹配。可以得到最多能配多长。

然后就能过了。

【时间复杂度】O(Len*Sum) Len为第一个串的长度。Sum为所有串的字母数之和。

【空间复杂度】O(Sum)

【CODE】

#include

[HDOJ1403 Longest Common Substring]【后缀数组】

【题目大意】求两个串的最长公共前缀。
【算法分析】
后缀数组,利用height数组高一下即可。会后缀数组的都会本题。。。
【其它】
1Y。
以前基数排序用邻接表写的,现在换了线性数组写。
另外也算省赛前对后缀数组的一个小复习吧。
【CODE】
#include #include #include const int N=205555;
const int LL=sizeof(int)*3;
int n,cut;
char str[N],s1[N],s2[N];
int sa[N],rank[N],Sum[N],a[N][3],b[N][3],height[N];

void Sort(){
for (int i,k=1;k>=0;k–){
for (i=0;i<=n;i++) Sum[i]=0;
for (i=1;i<=n;i++) Sum[a[i][k]+1]++;
for (i=1;i<=n;i++) Sum[i]+=Sum[i-1];
for (i=1;i<=n;i++) memcpy(&b[++Sum[a[i][k]]],&a[i],LL);
memcpy(&a[1],&b[1],LL*n);
}
}

void make_suffix_arr(){
int i,cnt=0,k,s;
for (i=0;i<256;i++) Sum[i]=0;
for (i=1;i<=n;i++) Sum[str[i]]++;
for (i=0;i<256;i++)
if (Sum[i])
Sum[i]=++cnt;
for (i=1;i<=n;i++) rank[i]=Sum[str[i]];
for (k=1;1< s=1<<(k-1);
for (i=1;i<=n;i++){
a[i][0]=rank[i];
if (i+s<=n) a[i][1]=rank[i+s];
else a[i][1]=0;
a[i][2]=i;
}
Sort();
for (cnt=0,i=1;i<=n;rank[a[i][2]]=cnt,i++)
cnt+=(!cnt || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]);
}
for (i=1;i<=n;i++) sa[rank[i]]=i;
}

inline int max(int x,int y){return x>y?x:y;}

void make_height(){
int i,j,k,st;
for (i=1;i<=n;i++){
if (rank[i]==1) continue;
st=max(0,height[rank[i-1]]-1);
j=i+st; k=sa[rank[i]-1]+st;
while (j<=n && k<=n && str[j]==str[k]){j++; k++; st++;}
height[rank[i]]=st;
}
}

void reply(){
int ans=0;
for (int i=3;i<=n;i++)
if ((sa[i-1] || (sa[i-1]>cut && sa[i] ans=max(ans,height[i]);
printf("%dn",ans);
}

int main(){
int L1,L2;
while (scanf("%s%s",s1+1,s2+1)!=EOF){
n=0;
L1=strlen(s1+1);
L2=strlen(s2+1);
memcpy(str+1,s1+1,sizeof(char)*L1);
str[L1+1]=’.’;
cut=L1+1;
memcpy(str+L1+2,s2+1,sizeof(char)*L2);
n=L1+L2+1;
make_suffix_arr();
make_height();
reply();
}
}