首页 > 代码库 > hdu 4416 Good Article Good sentence(后缀数组&思维)

hdu 4416 Good Article Good sentence(后缀数组&思维)

2024-07-24 01:52:00   224人阅读

Good Article Good sentence

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2308    Accepted Submission(s): 649


Problem Description
In middle school, teachers used to encourage us to pick up pretty sentences so that we could apply those sentences in our own articles. One of my classmates ZengXiao Xian, wanted to get sentences which are different from that of others, because he thought the distinct pretty sentences might benefit him a lot to get a high score in his article.
Assume that all of the sentences came from some articles. ZengXiao Xian intended to pick from Article A. The number of his classmates is n. The i-th classmate picked from Article Bi. Now ZengXiao Xian wants to know how many different sentences she could pick from Article A which don‘t belong to either of her classmates?Article. To simplify the problem, ZengXiao Xian wants to know how many different strings, which is the substring of string A, but is not substring of either of string Bi. Of course, you will help him, won‘t you?
 

Input
The first line contains an integer T, the number of test data.
For each test data
The first line contains an integer meaning the number of classmates.
The second line is the string A;The next n lines,the ith line input string Bi.
The length of the string A does not exceed 100,000 characters , The sum of total length of all strings Bi does not exceed 100,000, and assume all string consist only lowercase characters ‘a‘ to ‘z‘.
 

Output
For each case, print the case number and the number of substrings that ZengXiao Xian can find.
 

Sample Input
3
2
abab
ab
ba
1
aaa
bbb
2
aaaa
aa
aaa
 

Sample Output
Case 1: 3
Case 2: 3
Case 3: 1
 

Source
2012 ACM/ICPC Asia Regional Hangzhou Online
 

Recommend
liuyiding   |   We have carefully selected several similar problems for you:  5041 5040 5039 5038 5037 
 题意：
给你一个a串长度最多1e5。然后n个b串.所有b串的总长度不超过1e5.现在问你a有多少个不同且不是任何一个b的子串的子串。
思路：
感觉跟后缀数组求有多少个不同的子串方法类似。难点在于怎么处理不是b的子串的问题。首先肯定是把所有串连起来。中间用$符号隔开。注意数组要开大一点。为此就re一发。然后对于所有sa[i]<lenA的位置，lenA为A串的串长。
lenA-sa[i]就是A串的i号后缀共对应多少子串。lenA-sa[i]-height[i]就是该位置比上个位置多出来多少个不同的子串。
lenA-sa[i]-height[i]-LCP[i,j].j为i下面第一个b的后缀。就是去掉和b相同的子串后剩下多少不同子串的个数啦。对于LCP[i,j]怎么求。从后往前扫一遍就行了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=350010;
typedef long long ll;
char txt[maxn];
int sa[maxn],T1[maxn],T2[maxn],ct[maxn],he[maxn],rk[maxn],ans,n,m,lena;
int bi[maxn];
void getsa(char *st)
{
    int i,k,p,*x=T1,*y=T2;
    for(i=0; i<m; i++) ct[i]=0;
    for(i=0; i<n; i++) ct[x[i]=st[i]]++;
    for(i=1; i<m; i++) ct[i]+=ct[i-1];
    for(i=n-1; i>=0; i--)
        sa[--ct[x[i]]]=i;
    for(k=1,p=1; p<n; k<<=1,m=p)
    {
        for(p=0,i=n-k; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(i=0; i<m; i++) ct[i]=0;
        for(i=0; i<n; i++) ct[x[y[i]]]++;
        for(i=1; i<m; i++) ct[i]+=ct[i-1];
        for(i=n-1; i>=0; i--) sa[--ct[x[y[i]]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,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++;
    }
}
void gethe(char *st)
{
    int i,j,k=0;
    for(i=0;i<n;i++) rk[sa[i]]=i;
    for(i=0;i<n-1;i++)
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(st[i+k]==st[j+k]) k++;
        he[rk[i]]=k;
    }
}
int main()
{
    int t,cas=1,nm,i,nl,tp,bb;
    ll ans;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&nm);
        scanf("%s",txt);
        n=lena=strlen(txt);
        for(i=0;i<nm;i++)
        {
            txt[n++]='$';
            scanf("%s",txt+n);
            nl=strlen(txt+n);
            n+=nl;
        }
        m=150;
        n++;
        getsa(txt);
        gethe(txt);
        n--;
        ans=bb=0;
        for(i=n;i>=1;i--)
        {
            if(sa[i]>=lena)
                bb=he[i];
            else
               bi[i]=bb,bb=min(bb,he[i]);
        }
        for(i=1;i<=n;i++)
        {
            if(sa[i]<lena)
            {
                tp=lena-sa[i]-min(lena-sa[i],max(he[i],bi[i]));
                ans+=tp;
            }
        }
        printf("Case %d: %I64d\n",cas++,ans);
    }
    return 0;
}


hdu 4416 Good Article Good sentence(后缀数组&思维)


联系
我们