后缀数组之前一直在给队友搞，但是这个类太大了，预感到青岛八成会有，于是自己也学习一下，记录一下做题的历程
所用的模板暂时来自于队友的倍增nlogn da算法
int t1[maxn] , t2[maxn] , c[maxn] ;
bool cmp(int *r , int a , int b , int l) {
return r[a] == r[b] && r[a+l] == r[b+l] ;
}
void da(int s[], int sa[], int ra[], int he[], int n, int m) {
n ++ ;
int i , j , p , *x = t1, *y = t2;
for(i = 0 ; i < m ; i ++ ) c[i] = 0 ;
for(i = 0 ; i < n ; i ++ ) c[x[i] = s[i]] ++ ;
for(i = 1 ; i < m ; i ++ ) c[i] += c[i-1] ;
for(i = n - 1 ; i >= 0 ; i -- ) sa[--c[x[i]]] = i;
for(j=1;j<=n;j<<=1)
{
p=0;
for(i = n-j; i<n;i++) y[p++] = i ;
for(i = 0 ; i < n ; i ++ ) {
if(sa[i] >= j) y[p++] = sa[i] - j;
}
for(i = 0 ; i < m ; i ++ ) c[i] = 0 ;
for(i = 0 ; i < n ; i ++ ) c[x[y[i]]] ++ ;
for(i = 1 ; i < m ; i ++ ) c[i] += c[i-1] ;
for(i = n - 1 ; i >= 0 ; i --) sa[--c[x[y[i]]]] = y[i] ;
swap(x,y) ;
p = 1 ; x[sa[0]] = 0 ;
for(i = 1 ; i < n ; i ++ ) {
x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
if(p>=n)break;
m=p;
}
int k=0;
n--;
for(i = 0 ; i <= n ; i ++ ) ra[sa[i]] = i;
for(i = 0 ; i < n ; i ++ ) {
if(k) k -- ;
j = sa[ra[i]-1];
while(s[i+k] == s[j+k]) {
k ++ ;
//printf("%d %d %d
" , i,j,k ) ;
}
he[ra[i]] = k ;
}
}
int ra[maxn] , he[maxn] ;
int rmq[maxn] ;
int mm[maxn] ;
int min1[maxn][25] ;
void init_rmq(int n) {
memset(min1, 0 , sizeof(min1)) ;
for(int i = 1 ; i <= n ; i ++ ) min1[i][0] = he[i] ;
int l = int(log((double)n)/log(2.0)) ;
for(int j = 1 ; j <= l ; j ++ ) {
for(int i = 1 ; i + (1<<j-1) - 1 <= n ; i ++ ) {
min1[i][j] = min(min1[i][j-1] , min1[i+(1<<(j-1))][j-1]) ;
}
}
}
int ask(int l,int r) {
int k = int(log(double(r-l+1))/log(2.0));
return min(min1[l][k], min1[r-(1<<k) + 1][k]) ;
}
int lcp(int a,int b) {
int ar = ra[a] , br = ra[b] ;
if (ar > br) swap(ar,br) ;
return ask(ar+1,br) ;
}
int s[maxn] ;
int sa[maxn] ;
敲错模板是个很头疼的事情，耗费了许多时间
求不同子串数目
子串一定是一个后缀的前缀，进行字符串排序后，相邻rank的两个字符串一定有共同的前缀(即使长度为0)，所以在统计前缀的时候，对于相同的前缀，永远只统计后者在前者中未出现的前缀，因为前者的独有前缀也将在其作为后者时被计算到。
当然这其实就是height数组的概念。。
char S[maxn] ;
int main () {
int t ;
scanf("%d" , &t) ;
while(t -- ) {
scanf("%s" , S) ;
int n = strlen(S) ;
for(int i = 0 ; i < n; i ++ ) {
s[i] = int(S[i]) ;
}
s[n] = 0 ;
da(s,sa,ra,he,n,256);
for(int i=1;i<=n;i++)rmq[i] = he[i];
init_rmq(n) ;
int ans = 0 ;
for(int i=1;i<=n;i++){
int pos1 = sa[i] ;
int pos2 = sa[i-1] ;
int lc = lcp(pos1,pos2);
int len=n-(pos1 + lc);
ans += len ;
}
printf("%d
" , ans) ;
}
}
求出现至少k次的可重复子串
网上的题解多为二分ans，然后对height中施加限制，查看是否有k个，实际上不需这样做
我们认为子串一定是后缀的前缀，那么排序后缀后，相等的子串所代表的后缀一定是相邻的，所以对于排名为x的后缀，只需要寻找排名为x-k+1的后缀，然后看看它们的lcp就可以了
不过复杂度实际上没有二分ans快，因为预处理rmq其实也是nlogn的，甚至还会慢一些。
当子串元素过大的时候会跑的很慢，据说这个题虽然元素的大小为1e6但是实际上没有，可以通过离散化来将m降低到n的大小
int main () {
int n , k ;
while(scanf("%d%d" , &n,&k) != EOF) {
rep(i,0,n-1) scanf("%d" , &s[i]) ;
s[n] = 0 ;
da(s,sa,ra,he,n,1000000) ;
init_rmq(n);
int ans = 0 ;
rep(i,1,n) {
int pos1 = sa[i] ;
if(i-k+1 < 1) continue ;
int pos2 = sa[i-k+1] ;
ans = max(ans , lcp(pos1,pos2)) ;
}
printf("%d
" , ans) ;
}
}
POJ1743
求不重叠且出现多次的子串的最长长度
对于转置，我们可以保存差分，这样就把同类串给归类了
如果题目不要求不重叠，那么想必ans就是最大的height了，因为排序后相邻rank的字符串必定是最相似前缀
要求不重叠的话，由于LCP是rank相差越大越小，所以有资质满足lcp>k的串其实就那么一个区间，因为有些串因为相邻太近所以其实没有lcp那么大，所以需要特殊对待
这样其实就是n2的复杂度，对于每个后缀，二分需找他的lcp>k的区间，然后暴力check可以得到的重复子串的长度 然后t了
学习了一下二分ans的写法，感觉很酷，当我们二分出来ans之后，可以对height进行“分类”，由于我们知道lcp必然是大于我们这个ans的，而一段height的最小值必须要大于等于ans
所以我们可以维护这个height连续>=二分ans的区间的pos的最大值和最小值，在这个区间无法维护时，也就是当前我们认为可能构成答案的子串的rank区间已经得出时，重置最大最小值。
其实写起来代码量还是很少的。。
bool check(int len) {
int minn = 999999999 ;
int maxx = -999999999 ;
for(int i = 1 ; i <= n ; i ++ ) {
if(he[i] >= len) {
minn = min(minn,min(sa[i],sa[i-1])) ;
maxx = max(maxx,max(sa[i],sa[i-1])) ;
if(minn + len < maxx) {
return true;
}
}
else {
minn = 999999999 ;
maxx = -999999999 ;
}
}
return false ;
}
int main () {
while(scanf("%d" , &n) != EOF) {
if( n == 0 ) break;
rep(i,0,n-1) scanf("%d" , &s[i]) ;
rep(i,0,n-1) ss[i] = s[i] ;
for(int i = n - 1 ; i >= 1 ; i -- ) s[i] = s[i] - s[i-1] + 95 ;
s[n] = 1 ;
s[0] = 2 ;
da(s , sa,ra,he,n,200) ;
init_rmq(n) ;
int res = -1 ;
int l = 0 , r = n ;
while(l <= r) {
int mid = (l + r) / 2 ;
if (check(mid)) {
res = mid ;
l = mid + 1 ;
}
else {
r = mid - 1 ;
}
}
if(res < 4) printf("0
") ;
else printf("%d
" , res+1) ;
}
}
POJ2406
判断一个串是否由一个串多次重复而来
做法是对串长度n求其约数, sqrt(n)，然后暴力判断其与我们想象的最后一段求lcp，这个lcp应当是我们想出来的子串长度，把所有可能的子串尝试一遍。
因为串长1e6，所以直接上nlogn的da会T,虽然我get到的是mle...据说是dc3，留待之后有时间写一下，zls号称自己写这个板子无敌，我信了。
POJ2774
求两个字符串的最长公共子串 长度为1e5，不可dp
做法是将两个字符串拼接起来，中间用个分隔符，按照ans和height分类，同一类中只要同时存在左右两个串的子串就ok
运用到两个思想 分类height和拼接两个字符串，前者避免了我们去寻找height区间和check，后者使得我们可以将两个串的sa放在一起考虑，处理多串有用
int n , m ;
int pren ;
bool check(int x) {
bool A = false , B = false ;
for(int i = 1 ; i <= n ; i ++ ) {
if(he[i] >= x) {
int pos1 = sa[i] ;
int pos2 = sa[i-1] ;
if(pos1 < pren) A = true ;
else B = true ;
if(pos2 < pren) A = true ;
else B = true ;
if(A && B) return true ;
}
else {
A = B = false ;
}
}
return false ;
}
int main () {
scanf("%s" , S) ;
n = strlen(S) ;
pren = n ;
for(int i = 0 ; i < n ; i ++ ) s[i] = S[i] - 'a' + 1 ;
s[n] = 27 ;
scanf("%s" , S) ;
int n2 = strlen(S) ;
for(int i = 0 ; i < n2 ; i ++ ) s[n+i+1] = S[i] - 'a' + 1 ;
n += (n2 + 1) ;
s[n] = 0 ;
da(s,sa,ra,he,n,28) ;
int l = 0 , r = n2 ;
int res = 0 ;
while(l <= r) {
int mid = (l + r) / 2 ;
if (check(mid)) {
res = mid ;
l = mid + 1 ;
}
else {
r = mid - 1 ;
}
}
printf("%d
" , res) ;
}
POJ3294
求在n个串中至少k个串的最长公共子串
n个串连接，排序后二分ans并进行分组，对同组check是否够k个了，因为要求记录ans，因为这一组都满足，所以ans直接选i就可以了
由于连接两个串的时候，我们使用一个未曾出现过的字符做分隔符，是为了避免abbbbc#aacaa这种情况，如果不加c就会影响我们的判断，导致ans=caa，那么如果多个串相连，我们每次都需要采用未曾出现过的字符做分隔符。
void flushans(){
ansnum = M ;
for(int i = 0 ; i < M ; i ++ ) ans[i] = tmp[i] ;
}
int getpos(int pos) {
for(int i = 1 ; i <= N-1 ; i ++ ) {
if(pos > endpos[i] && pos <= endpos[i+1]) return i+1 ;
}
return 1 ;
}
bool check(int mid) {
M = 0 ;
int mp[1005] ;
memset(mp,0,sizeof(mp)) ;
int cnt = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
int pos = i ;
cnt = 0 ;
while(pos <= n && he[pos] >= mid) {
int pos1 = sa[pos] ;
int pos2 = sa[pos-1] ;
int s1 = getpos(pos1) ;
int s2 = getpos(pos2) ;
if(mp[s1] == 0) {
mp[s1] = 1 ; cnt ++ ;
}
if(mp[s2] == 0) {
mp[s2] = 1 ; cnt ++ ;
}
pos ++ ;
}
if (cnt >= N/2+1) {
tmp[M++] = sa[i] ;
}
for(int j = i ; j < pos ; j ++ ) {
int pos1 = sa[j] ;
int pos2 = sa[j-1] ;
int s1 = getpos(pos1) ;
int s2 = getpos(pos2) ;
mp[s1] = mp[s2] = 0 ;
}
i = pos ;
}
if(M > 0) return true ;
return false ;
}
int main () {
bool f = false;
while(scanf("%d" , &N) != EOF) {
if(N == 0) break ;
if (f) printf("
") ;
f = true ;
int m = 26 ;
n = 0 ;
for (int i = 1 ; i <= N ; i ++ ) {
scanf("%s" , S) ;
int len = strlen(S) ;
if (i != 1) s[n++] = ++m ;
for(int j = 0 ; j < len ; j ++ ) {
s[n++] = S[j] - 'a' + 1 ;
}
endpos[i] = n ;
}
s[n] = 0 ;
da(s,sa,ra,he,n,m+1) ;
int res = 0 ;
int l = 0 , r = 1050 ;
while(l <= r) {
int mid = (l + r) / 2 ;
if(check(mid)) {
res = mid ;
l = mid + 1 ;
flushans() ;
}
else {
r = mid - 1 ;
}
}
if (res == 0) {
printf("?
") ;
}
else {
for(int i = 0 ; i < ansnum ; i ++ ) {
int pos = ans[i] ;
for(int i = 0 ; i < res ; i ++) {
printf("%c" , 'a'+s[pos+i]-1) ;
}
printf("
") ;
}
}
}
}
求在所给n个串中存在至少两个不相交的最长子串
二分ans，分组后对每组check每个串的最左和最右出现地点
int getpos(int x) {
for(int i = 1 ; i < N ; i ++ ) {
if(x > endpos[i] && x <= endpos[i+1]) return i + 1 ;
}
return 1 ;
}
bool check(int mid) {
int mp[15][2] ;
for(int i = 1; i <= N ; i ++ ) {
mp[i][0] = 999999999 ;
mp[i][1] = -999999999 ;
}
for(int i = 1 ; i <= n ; i ++ ) {
if(he[i] >= mid) {
int s1 = getpos(sa[i]) ;
int s2 = getpos(sa[i-1]) ;
mp[s1][0] = min(mp[s1][0] , sa[i]) ;
mp[s1][1] = max(mp[s1][1] , sa[i]) ;
mp[s2][0] = min(mp[s2][0] , sa[i-1]) ;
mp[s2][1] = max(mp[s2][1] , sa[i-1]) ;
}
else {
bool ok = true ;
for(int j = 1; j <= N ; j ++ ) {
if(mp[j][1] - mp[j][0] < mid) ok = false ;
}
if(ok) return true;
for(int j = 1; j <= N ; j ++ ) {
mp[j][0] = 999999999 ;
mp[j][1] = -999999999 ;
}
}
}
bool ok = true ;
for(int i = 1; i <= N ; i ++ ) {
if(mp[i][1] - mp[i][0] < mid) ok = false ;
}
if(ok) return true;
return false ;
}
int main () {
int t ; scanf("%d" , &t) ;
while(t -- ) {
scanf("%d" , &N) ;
n = 0 ;
m = 26 ;
for(int i = 1 ; i <= N ; i ++ ) {
if (i != 1) {
s[n++] = ++m ;
}
scanf("%s" , S) ;
int len = strlen(S) ;
for(int j = 0 ; j < len ; j ++ ) {
s[n++] = S[j] - 'a' + 1 ;
}
endpos[i] = n ;
}
s[n] = 0 ;
da(s,sa,ra,he,n,m+100) ;
int res = -1 ;
int l = 0 , r = 10000 ;
while( l <= r ) {
int mid = (l + r) / 2 ;
if(check(mid)) {
res = mid ;
l = mid + 1 ;
}
else {
r = mid - 1 ;
}
}
printf("%d
" , res) ;
}
}
POJ1226
求多串的公共子串x的长度，要求是该串还有x 或 x的反向
将一个串变为它和它的反向串的连接，中间加连接符，认为它们还是原来那个串，二分ans后分组
int getpos(int x) {
for(int i = 1 ; i < N ; i ++ ) {
if(x > endpos[i] && x <= endpos[i+1]) return i + 1 ;
}
return 1 ;
}
bool check(int mid) {
int mp[105] ;
for(int i = 1; i <= N ; i ++ ) {
mp[i] = 0 ;
}
for(int i = 1 ; i <= n ; i ++ ) {
if(he[i] >= mid) {
int s1 = getpos(sa[i]) ;
int s2 = getpos(sa[i-1]) ;
mp[s1] ++ ;
mp[s2] ++ ;
}
else {
bool ok = true ;
for(int j = 1; j <= N ; j ++ ) {
if (mp[j] <= 0) ok = false ;
}
if(ok) return true;
for(int j = 1; j <= N ; j ++ ) {
mp[j] = 0 ;
}
}
}
bool ok = true ;
for(int i = 1; i <= N ; i ++ ) {
if(mp[i] <= 0) ok = false ;
}
if(ok) return true;
return false ;
}
int main () {
int t ; scanf("%d" , &t) ;
while(t -- ) {
scanf("%d" , &N) ;
n = 0 ;
m = 256 ;
for(int i = 1 ; i <= N ; i ++ ) {
if (i != 1) {
s[n++] = ++m ;
}
scanf("%s" , S) ;
int len = strlen(S) ;
for(int j = 0 ; j < len ; j ++ ) {
s[n++] = S[j] ;
}
s[n++] = ++m ;
for(int j = len-1 ; j >= 0 ; j -- ) {
s[n++] = S[j] ;
}
endpos[i] = n ;
}
s[n] = 0 ;
da(s,sa,ra,he,n,m+100) ;
int res = -1 ;
int l = 0 , r = 100 ;
while( l <= r ) {
int mid = (l + r) / 2 ;
if(check(mid)) {
res = mid ;
l = mid + 1 ;
}
else {
r = mid - 1 ;
}
}
printf("%d
" , res) ;
}
}
在所给串后添加尽量少的字母使其成为回文串
题目可以转化为求所给串的后缀回文串的最长长度，将所给串的反串拼接在后面，就可以使用lcp枚举回文串中心判断了
int trans(char a) {
if (a <= 'z' && a >= 'a') return (a - 'a' + 1) ;
else return (a - 'A' + 1 + 26) ;
}
int main () {
while(scanf("%s" , S) != EOF) {
int len = strlen(S) ;
for(int i = 0 ; i < len ; i ++ ) s[i] = trans(S[i]) ;
n = len ;
s[n++] = 60 ;
for(int i = len - 1; i >= 0 ; i -- ) s[n++] = trans(S[i]) ;
s[n] = 0 ;
da(s,sa,ra,he,n,100) ;
init_rmq(n) ;
int maxlen = 0 ;
for(int i = 1 ; i <= len ; i ++ ) {
int lc = lcp(len - i, len + i) ;
if (len - i + lc - 1 >= len - 1) maxlen = max((lc * 2 - 1), maxlen) ;
}
for(int i = 1 ; i <= len - 1 ; i ++ ) {
int lc = lcp(len - i , len + i + 1) ;
if (len - i + lc - 1 >= len - 1) maxlen = max(lc*2 , maxlen) ;
}
printf("%s" , S) ;
for(int i = len - maxlen - 1 ; i >= 0 ; i -- ) printf("%c" , S[i]) ;
printf("
") ;
}
}
POJ3581
给出一个串，将其分作三段，分别反置，使之后的串字典序最小，a[1] > a[other]
第一段肯定是反置整个串，排序后缀后取最小的那个，且位置得给后两个串机会，因为a[1]是极大的，所以不影响后面
那么问题就变成了"给出一个串，分作两段，分别反置，使之后的串字典序最小"，如果还按照之前的方法做可能会出问题
所给串若是s1s2...sksk+1....sn-1sn,那么我们选择第一段s1~sk,反转后就是sk~s1 sn~sk+1，它的内在和k无关，是sn~s1 sn~s1的子串！
于是问题就变成了，求一个len = n*2的串中长度为n的最小子串了，我们排序一下，取位置为1~n-1为开头的后缀，这个后缀的长度虽然有可能>n，但是我们保证它的前n位一定是可选的后缀的前n位中最大的，因为即使算n+1位我们也不会输
vector<int>b ;
int main () {
b.clear() ;
scanf("%d" , &n) ;
for(int i = 0 ; i < n ; i ++ ) {
scanf("%d" , &s[i]) ;
b.push_back(s[i]) ;
}
sort(b.begin(), b.end()) ;
b.erase(unique(b.begin(),b.end()),b.end()) ;
for(int i = 0 ; i < n ; i ++ ) s[i] = lower_bound(b.begin(),b.end(),s[i]) - b.begin() + 1 ; /// 1 ~ n
/*
int maxx = s[0] , pos = 0 ;
for(int i = 1 ; i < n - 2; i ++ ) {
if(s[i] <= maxx) {
maxx = s[i] ;
pos = i ;
}
}
*/
for(int i = 0 ; i < n / 2 ; i ++ ) swap(s[i] , s[n-i-1]) ;
s[n] = 0 ;
da(s,sa,ra,he,n,200050) ;
int pos ;
for(int i = 1 ; i <= n ; i ++ ) {
int po = sa[i] ;
if(po > 1) {
pos = po ; break ;
}
}
for(int i = pos ; i < n ; i ++ ) printf("%d
" , b[s[i]-1]) ;
pos = n - pos - 1 ;
for(int i = 0 ; i < n / 2 ; i ++ ) swap(s[i] , s[n-i-1]) ;
int nn = n - pos - 1;
for(int i = 0 ; i < nn ; i ++ ) {
s[i] = s[pos + i + 1] ;
}
n = nn ;
for(int i = 0 ; i < n / 2 ; i ++ ) swap(s[i] , s[n-i-1]) ;
for(int i = 0 ; i < n ; i ++ ) s[n + i] = s[i] ;
n += n ;
s[n] = 0 ;
da(s,sa,ra,he,n,200050) ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
int pos = sa[i] ;
if(pos >= 1 && pos < nn) {
ans = pos ; break ;
}
}
for(int i = 0 ; i < nn ; i ++ ) printf("%d
" , b[s[ans+i]-1]) ;
}
求所给串中的一个子串，能最多被多少个小串重复而来
很精妙的思想，由三点组成
1 如果枚举长度len，且我认为可能有一个子串被三个小串重复而来，那么s[0] s[len] s[len*2]...它一定要覆盖三个点，这是长度必须的
如果我们认为是两个小串，就可以对s[x] 和 s[pos]求lcp，如果lcp能够覆盖住s[pos] ~ s[pos + len - 1]，那么毫无疑问是可以的，但是三个呢？我们不能这样暴力去求
2 然而，如果对s[x]和s[pos]求lcp，lcp很长，说明后面有好多个重复小串，因为一旦s[x]和s[pos]是不同的字符，那么后面肯定也是扭曲的很有规律的串，所以对两个点求lcp就可以求出，假设这两个点是我覆盖的三个点中的前两个，如果lcp能够覆盖到s[pos] ~ s[pos + len * 2 - 1] ， 那么我求s[pos]和s[pos+len]的lcp，结果也是一样的
3 如果答案是aabaab，而此时我的x=1，pos=4，这时候lcp只能覆盖到5，我就会误算，认为只能由一个小串构成，怎么办？
我如果误算了，就会少算一个，绝对不会少算多个，对于每次我枚举覆盖的第一个点和第二个点，我都尝试根据所得lcp进行“修正”，尝试让结果+1，如果当前所求的lcp还差一位就能/len的结果更大，使ans+1，那我就让x和pos往前移动一位，看看是否真的增大了结果。
int main () {
int t ; scanf("%d" , &t) ;
while(t -- ) {
int n ; scanf("%d" , &n) ;
for(int i = 0 ; i < n ; i ++ ) {
char SS[2]; scanf("%s" , SS) ;
s[i] = SS[0] - 'a' + 1 ;
}
s[n] = 0 ;
da(s,sa,ra,he,n,10) ;
init_rmq(n) ;
int ans = 0 ;
for(int len = 1 ; len <= n ; len ++ ) {
for(int pos = 0 ; pos + len < n ; pos += len) {
int qlen = lcp(pos,pos+len) ;
ans = max(ans , qlen / len + 1) ;
int need = len - qlen % len ; need %= len ;
if(pos - need >= 0) {
qlen = lcp(pos - need, pos-need+len) ;
ans = max(ans , qlen / len + 1) ;
}
}
}
printf("%d
" , ans) ;
}
}
上题的升级版，需要输出那个子串
我们可以在更新ans的时候记录，不过当ans == qlen / len + 1时我们无法确定谁更强，虽然我们排过序了，但是dcdcb的时候我们会认为dcb比较优秀，因为我们排序的时候未曾去了解过长度，但是在更新那个最小子串的时候是有长度这个限制的
我们会发现当ab两个串长度不同，重复次数相同，且短串是长串的子串的时候才会发现错误，于是我们枚举rank，然后把所有可行解从小到大check一遍就行了
vector<int>b ;
int main () {
int t ; scanf("%d" , &t) ;
int cas = 1 ;
while(scanf("%s" , S) != EOF) {
n = strlen(S) ;
if(n == 1 && S[0] == '#') break ;
for(int i = 0 ; i < n ; i ++ ) s[i] = S[i] - 'a' + 1 ;
s[n] = 0 ;
da(s,sa,ra,he,n,100) ;
init_rmq(n) ;
int ans = 0 ;
int le = 0;
for(int len = 1 ; len <= n ; len ++ ) {
for(int pos = 0 ; pos + len < n ; pos += len) {
int qlen = lcp(pos,pos+len);
if(qlen / len + 1 > ans) {
ans = qlen / len + 1 ;
le = len ;
b.clear() ;
b.push_back(pos) ;
}
else if (qlen / len + 1 == ans) {
b.push_back(pos) ;
}
int need = len - qlen % len ; need %= len ;
if(pos - need >= 0) {
qlen = lcp(pos - need , pos - need + len) ;
if (qlen / len + 1 > ans) {
ans = qlen / len + 1 ;
le = len ;
b.clear() ;
b.push_back(pos-need) ;
}
else if (qlen / len + 1 == ans) {
b.push_back(pos-need) ;
}
}
}
}
printf("Case %d: ", cas ++ ) ;
if (ans == 0) {
printf("%c" , s[sa[1]]) ;
}
else {
bool fin = false ;
for (int i = 1 ; i <= n ; i ++ ) {
if(fin) break ;
for(int j = 0 ; j < b.size(); j ++ ) {
int pos = sa[i] ;
if (pos + le < n) {
int lc = lcp(pos,pos+le) ;
if ((lc+le)/le >= ans) {
fin=true;
for(int k = 0 ; k < ans * le ; k ++) {
printf("%c" , 'a' + s[k + pos] - 1) ;
}
printf("
") ;
break;
}
}
}
}
}
}
}
求AB两串中长度>=k的相同子串对的数目
如果我们sort完，按照he>=k进行分类之后，从左往右，每扫到一个A的串都可以向前暴力寻找B的串计数，但是这样就太暴力了
对同一组，我们会意识到，如果有b1 b2 a三个串，a和b2的lcp >= a和b1的lcp，这个满足单调性，于是我们可以对同一组算两次，第一次算A，将所有的B的height和数量(1)加入栈，算一次a，这时候的贡献是栈中的he总和，之后我们再压入B的时候，如果这个新的height比栈顶的小，说明这时候A的子串不能再和栈中的串有那么大的lcp，于是我们将栈中的串的height对sum的贡献更改为新的height，这就是单调栈的用法，计算B的时候同理。
L getpos(L x) {
if(x <= pren) return 0 ;
else return 1 ;
}
stack<int>a ;
stack<int>b ;
int main () {
while(scanf("%lld" , &k) != EOF) {
if( k == 0 ) break ;
scanf("%s" , S) ;
L len = strlen(S) ;
n = 0 ;
for(L i = 0 ; i < len ; i ++ ) s[n ++ ] = S[i] ;
s[n ++ ] = 270 ;
pren = n - 1;
scanf("%s" , S) ;
len = strlen(S) ;
for(L i = 0 ; i < len ; i ++ ) s[n ++ ] = S[i] ;
s[n] = 0 ;
da(s,sa,ra,he,n,300);
L ans = 0 ;
L sum = 0 ;
for(L i = 1 ; i <= n ; i ++ ) {
L pos = i ;
while(pos <= n && he[pos] >= k) pos ++ ;
/// A
while(!a.empty())a.pop();
while(!b.empty())b.pop();
sum = 0 ;
for(L j = i ; j < pos ; j ++ ) {
L pos1 = sa[j-1] ;
L num = 0 ;
if(getpos(pos1) == 1) { /// last = B
num ++ ;
sum += he[j] - k + 1 ;
}
while(!a.empty()) {
L he1 = a.top() , num1 = b.top() ;
if(he[j] <= he1) {
a.pop() ;
b.pop() ;
num += num1 ;
sum -= (he1 - he[j]) * num1 ;
}
else {
break ;
}
}
a.push(he[j]) ;
b.push(num) ;
L pos2 = sa[j] ;
if(getpos(pos2) == 0) { /// now calc A
ans += sum ;
}
}
/// B
while(!a.empty())a.pop();
while(!b.empty())b.pop();
sum = 0 ;
for(L j = i ; j < pos ; j ++ ) {
L pos1 = sa[j-1] ;
L num = 0 ;
if(getpos(pos1) == 0) { /// last = A
num ++ ;
sum += he[j] - k + 1 ;
}
while(!a.empty()) {
L he1 = a.top() , num1 = b.top() ;
if(he[j] <= he1) {
a.pop() ;
b.pop() ;
num += num1 ;
sum -= (he1 - he[j]) * num1 ;
}
else {
break ;
}
}
a.push(he[j]) ;
b.push(num) ;
L pos2 = sa[j] ;
if(getpos(pos2) == 1) { /// now calc B
ans += sum ;
}
}
i = pos ;
}
printf("%lld
" , ans) ;
}
}
kuangbin专题基本做完了，接下来做一下近两年的多校&online&onsite的题目
16ec的题目，给n个串，找出第一个串的最短子串使其不在其余串中出现
陷入了一个坑，之前都是最长，于是可以二分ans然后分组check，现在二分完发现没有办法很好的check
思考几个性质：1 假如后缀A和后缀B的lcp为3，那么后缀A的前3项一定在B中出现过了，前4项则未必
2 假如存在后缀ABC，她们的rank依次，则lcp(b,c) >= lcp(a,c)
于是我们排序后，就可以对所有的第一个串的后缀check，找到她左边第一个非第一个串的后缀，求lcp为x，那么它的前x项一定不是答案。然后再寻找右边的第一个非第一个串的后缀，求lcp为y，那么就可以得出答案，该后缀的前max(x,y)+1项是答案，不过需要判断这些项是否超出了第一个串的size
通过这道题感觉到，板子只是一个板子，我们可以对后缀进行排序而已，剩下的东西都没有定式，我们只是得到了一些有用的东西，需要做的还是在这些东西上蹦蹦跳跳
int lef[maxn] , rig[maxn] ;
void ycl() {
int last = -1 ;
for(int i = 1 ; i <= n ; i ++ ) {
lef[i] = last ;
if(getpos(sa[i]) == 2) last = i ;
}
last = -1 ;
for(int i = n ; i >= 1 ; i -- ) {
rig[i] = last ;
if(getpos(sa[i]) == 2) last = i ;
}
}
int main () {
int t ; scanf("%d" , &t) ;
int cas = 1 ;
while(t -- ) {
scanf("%d" , &N) ;
n = 0 ;
m = 30 ;
for(int i = 1 ; i <= N ; i ++ ) {
scanf("%s" , S) ;
int len = strlen(S) ;
if (i != 1) s[n ++ ] = ++ m ;
for(int j = 0 ; j < len ; j ++) s[n ++ ] = (S[j] - 'a' + 1) ;
endpos[i] = n - 1;
}
s[n] = 0 ;
da(s,sa,ra,he,n,50000 + 50) ;
ycl();
init_rmq(n);
int len = 999999999 , ans = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
if(getpos(sa[i]) == 1) {
int can = endpos[1] - sa[i] + 1 ;
int pos1 = sa[i] ;
int pos2 ;
int lc = 0 ;
if(lef[i] != -1) {
pos2 = sa[lef[i]] ;
lc = max(lcp(pos2,pos1),lc);
}
if(rig[i] != -1) {
pos2 = sa[rig[i]];
lc = max(lcp(pos2,pos1),lc);
}
if(can > lc) {
can = lc + 1 ;
if(can < len) {
len = can ;
ans = pos1;
}
else if(can == len){
if(ra[ans] > ra[pos1]) {
ans = pos1 ;
}
}
}
}
}
printf("Case #%d: " , cas ++ ) ;
if(len == 999999999) {
printf("Impossible
") ;
continue ;
}
for(int i = 0 ; i < len ; i ++ ) printf("%c" , 'a' + s[ans + i] - 1) ;
printf("
") ;
}
}
17Shenyang online 求一个串中严格出现k次的子串
所有的子串都是后缀的前缀，于是对于rank = i 来说，rank=i-k+1的前缀的lcp可能为ans做贡献
但是及时是i和i-k+1的lcp，也可能不是ans，因为要求严格出现k次，这个lcp可能出现>k次，如何限制？
我统计第i个串作为那些子串的最大rank的父串，假设第i-k+1个串是最小rank的父串，那么i-k和i+1号串不应当含有这些子串，于是用lcp乱统计一下就可以了
需要注意的是，因为lcp(a,a)会出问题导致rmq的计算RE，于是需要特判
int main () {
L t ; scanf("%lld" , &t) ;
while(t -- ) {
scanf("%lld" , &k) ;
scanf("%s" , S) ;
L len = strlen(S) ;
n = 0 ;
for(L i = 0 ; i < len ; i ++ ) s[n ++ ] = S[i] ;
s[n] = 0 ;
da(s,sa,ra,he,n,500) ;
init_rmq(n) ;
L ans = 0 ;
for(L i = k ; i <= n ; i ++ ) {
L pos1 = sa[i] ;
L pre = i - k + 1 ;
L lastpos = sa[pre] ;
L can ;
if(lastpos != pos1) {
can = lcp(lastpos,pos1) ;
}
else {
can = n - sa[i] ;
}
L l = 0 ;
L left = pre - 1 ;
if (left >= 1) {
L pos2 = sa[left] ;
L lc = lcp(pos1,pos2) ;
l = max(lc,l) ;
}
if(i + 1 <= n) {
L pos2 = sa[i+1] ;
L lc = lcp(pos1,pos2) ;
l = max(lc,l) ;
}
if(can > l) {
ans += can - l ;
}
}
printf("%lld
" , ans) ;
}
}
比赛结束了。。很难接受这个结果。。
可是以后的路还很长。。
在未曾涉足的领域要比对待算法更加努力的去学习啊！