HDU5853 Jong Hyok and String（二分 + 后缀数组）

时间：2021-11-30 12:10:31

题目

Source

http://acm.hdu.edu.cn/showproblem.php?pid=5853

Description

Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.

Input

First line contains T, a number of test cases.

For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m)

1 <= T <= 10
1 <= n <= 100000
1 <= m<= 500000
1 <=|Pi|<=100000
1 <=|Qi|<=100000
∑ni=1|Pi|≤100000
File size is less than 3.5 megabytes.

Output

For each test case, first line contains a line “Case #x:”, x is the number of the case.

For each question, you should print one integer in one line.

Sample Input

1
2 2
aba
ab
a
ab

Sample Output

Case #1:
1
2

分析

题目大概说给若干的字符串pi，然后若干个询问，询问pi内有多少个不同子串与给定的询问字符串的strange set相同。一个字符串的strange set是一个二元组(i,j)的集合，表示该字符串在pi中出现且最后一个字符在pi中的位置j。

这题比赛时和队友讨论了挺久的。

首先想到的是，与查询串的strange set相同一定是查询串的后缀（其实不止是这样= =）。而查询串后缀的strange set不与查询串相同的情况是这个后缀在pi中被匹配了，但在那个位置查询串没被匹配。

然后队友考虑到通过把串反转，将后缀转化成前缀。

接下去，看到Σ|pi|<=100000，所以开始往后缀数组上面想。自然，那些pi要反转（这时考虑的是前缀了），然后拼接起来，中间用特殊字符隔开。

而求得其各个后缀排序后，对于任何一个模式串是能通过二分去查找到它所在匹配位置。然后就开始考虑对于查询串的各个前缀，去通过二分其位置的上下界求得有多少个与其匹配，然后再与查询串匹配次数对比，如果相等说明该前缀是可行的。

不过时间复杂度显然不行。后面我想到如果前缀x不行，那么前缀x-1也一定不行，然后慢慢地得出了这个结论——

  • 对于各个查询串，通过两次二分，找到它匹配的上界upp和下界low（upp<=low。。），那么结果就是|查询串|-max(LCP(upp,upp-1),LCP(low,low+1))！

我们验证了时间复杂度，是所有查询串总长*logΣ|pi|，所有查询串总长Clarification说到200W左右，那样大概是可以一试的。于是就写了，不过WA= =二分改了改，然后什么什么。。比赛结束也没搞出来。

其实，一开始逻辑就有漏洞了。。【与查询串的strange set相同一定是查询串的后缀（其实不止是这样= =）】，还有一种情况！

比如这个数据：

1 1
bbbaa
bba 
结果应该是3，因为：
  • strange set(“bba”) = {(1,4)}
  • bba的这两个后缀满足：strange set(“bba”) = {(1,4)}、strange set(“ba”) = {(1,4)}
  • 此外还有这个满足：strange set(“bbba”) = {(1,4)}
就是说还有包含整个字符串的可能满足。然后我想了想，画了画，又得出结论：
  • 这种情况的数量就是上下界的LCP长度减去查询串的长度！
另外要注意上界=下界的情况，还有特殊字符在这儿应该要互不相同。。
 
感觉这题好难描述= =就这样吧。。最后我终于AC了。。
 

代码

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define INF (1<<30)

#define MAXN 222222

int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];

int cmp(int *r,int a,int b,int l){

    return r[a]==r[b] && r[a+l]==r[b+l];

}

int sa[MAXN],rnk[MAXN],height[MAXN];

void SA(int *r,int n,int m){

    int *x=wa,*y=wb;

    for(int i=0; i<m; ++i) ws[i]=0;

    for(int i=0; i<n; ++i) ++ws[x[i]=r[i]];

    for(int i=1; i<m; ++i) ws[i]+=ws[i-1];

    for(int i=n-1; i>=0; --i) sa[--ws[x[i]]]=i;

    int p=1;

    for(int j=1; p<n; j<<=1,m=p){

        p=0;

        for(int i=n-j; i<n; ++i) y[p++]=i;

        for(int i=0; i<n; ++i) if(sa[i]>=j) y[p++]=sa[i]-j;

        for(int i=0; i<n; ++i) wv[i]=x[y[i]];

        for(int i=0; i<m; ++i) ws[i]=0;

        for(int i=0; i<n; ++i) ++ws[wv[i]];

        for(int i=1; i<m; ++i) ws[i]+=ws[i-1];

        for(int i=n-1; i>=0; --i) sa[--ws[wv[i]]]=y[i];

        swap(x,y); x[sa[0]]=0; p=1;

        for(int i=1; i<n; ++i) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

    }

    for(int i=1; i<n; ++i) rnk[sa[i]]=i;

    int k=0;

    for(int i=0; i<n-1; height[rnk[i++]]=k){

        if(k) --k;

        for(int j=sa[rnk[i]-1]; r[i+k]==r[j+k]; ++k);

    }

}

int st[18][MAXN];

void ST(int *a,int n){

    for(int i=1; i<=n; ++i) st[0][i]=a[i];

    for(int i=1; i<18; ++i){

        for(int j=1; j<=n; ++j){

            if(j+(1<<i)>n) break;

            st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);

        }

    }

}

int rmq(int a,int b){

    if(a>b) swap(a,b);

    int k=(int)(log2(b-a+1)+1e-6);

    return min(st[k][a],st[k][b-(1<<k)+1]);

}

char str[MAXN];

int an,a[MAXN],b[MAXN],bn;

int len[MAXN];

int cmp(int k){

    int i;

    for(i=0; i+k<an && i<bn; ++i){

        if(a[i+k]>b[i]) return 1;

        else if(a[i+k]<b[i]) return -1;

    }

    if(i!=bn) return -1;

    return 0;

}

int main(){

    int t,n,m;

    scanf("%d",&t);

    for(int cse=1; cse<=t; ++cse){

        scanf("%d%d",&n,&m);

        an=0;

        for(int i=0; i<n; ++i){

            scanf("%s",str);

            for(int j=strlen(str)-1; j>=0; --j){

            	len[an]=j+1;

                a[an++]=str[j]-'a'+1;

            }

            a[an++]=28+i;

        }

        a[an++]=0;

        SA(a,an,28+n);

        ST(height,an-1);

        printf("Case #%d:\n",cse);

        while(m--){

            scanf("%s",str);

            bn=0;

            for(int j=strlen(str)-1; j>=0; --j){

                b[bn++]=str[j]-'a'+1;

            }

            int l=1,r=an-1;

            int upp=-1;

            while(l<=r){

                int mid=l+r>>1;

                int tmp=cmp(sa[mid]);

                if(tmp==0){

                    upp=mid;

                    r=mid-1;

                }else if(tmp>0) r=mid-1;

                else if(tmp<0) l=mid+1;

            }

            if(upp==-1){

                printf("%d\n",0);

                continue;

            }

            l=1,r=an-1;

            int low=-1;

            while(l<=r){

                int mid=l+r>>1;

                int tmp=cmp(sa[mid]);

                if(tmp==0){

                    low=mid;

                    l=mid+1;

                }else if(tmp>0) r=mid-1;

                else if(tmp<0) l=mid+1;

            }

            int tmp=0;

            if(upp!=1){

                tmp=max(tmp,height[upp]);

            }

            if(low!=an-1){

                tmp=max(tmp,height[low+1]);

            }

            if(upp==low) printf("%d\n",bn-tmp+len[sa[upp]]-bn);

            else printf("%d\n",bn-tmp+rmq(upp+1,low)-bn);

        }

    }

    return 0;

}

相关文章