POJ 3729 Facer's string (后缀数组)

题目大意:

串1中有多少个后缀和 串2中的某个后缀 的lcp 为 k

思路分析:

先找出 长度至少为k的对数有多少。

再找出 至少为k+1的有多少

然后相减。

#include #include #include #include #include #include #define maxn 110005 using namespace std; int str[maxn]; int sa[maxn],t1[maxn],t2[maxn],c[maxn],n; void suffix(int m) { int *x=t1,*y=t2; for(int i=0; i=0; i--)sa[--c[x[i]]]=i; for(int k=1; k=k)y[p++]=sa[i]-k; for(int i=0; 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)break; m=p; } } int rank[maxn],height[maxn]; void getheight() { int k=0; for(int i=0; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:uva 10368 - Euclid's Game(博弈)
下一篇:主席树初探 & bzoj 3295: [Cqoi2011] 动态逆序对 题解
相关文章

对于c/c++中的数组排序及计算平均值和

在c/c++中利用数组名和指针进行排序的

C/C++中多维数组的指针作为函数参数传

C/C++中数组和指针类型的关系的入门教

c/c++中的字符指针数组,指向指针的指针

C/C++数组名与指针区别深入探索

c++之字符数组型的静态成员初始化实例

C++ VS C#(5):数组

C++中的动态多维数组

C++中的动态多维数组

图文推荐

POJ 3729 Facer's string (后缀数组)
ZOJ 3640 Help Me
POJ 3729 Facer's string (后缀数组)
CF 518C(Anya and
POJ 3729 Facer's string (后缀数组)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-12 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.088 (s). 10 q(s)