[省選前題目整理][BZOJ 2754][SCOI 2012]喵星球上的點名(字尾數組)

題目連結

http://www.lydsy.com/JudgeOnline/problem.php?id=2754

題解

來自出題人滿滿的惡意。。。。

有兩種做法：1、AC自動機 2、字尾數組。

AC自動機做法很複雜，因為此題非常喪病地沒有限定字元集的大小，這樣就導緻不能用Trie樹傳統的儲存兒子的方式，隻能用map,并且這樣會讓最終的算法複雜度多一個 log 。

而字尾數組的做法就随意了很多，因為SA對字元集沒有什麼特别的要求，字元串都是可以看成是數字串，非常爽，果斷用SA。

SA的做法看上去就是亂搞：首先把所有貓的名的字元串、貓的姓的字元串、點名的字元串拼成一個大的字元串，每個不同的串之間用不同的分割符隔開，注意要不同的分割符，為了避免RP爆零時比對錯誤。

然後注意到題目的一個很重要的限制：一個貓被點名，點名串可以是它的姓的子串，也可是它的名的子串，但是絕對不能是它的姓和名拼起來的子串，是以每個貓的姓和名必須分開看待。

另外要注意到SA一個非常關鍵的性質：對于一些具有相同字首的字尾來說，他們的排名是挨在一起的，對于一個開頭下标為 t ，長為len的子串而言，包含它的字尾與開頭下标為 t 的字尾的LCP值一定是大于等于len的，據此，對于每個點名串 i ，我們可以暴力在height數組中掃一遍找出一個區間 [L,R] ，以這個區間中的數字 i 的sa[i]作為開頭下标的字尾都是包含第 i 個點名串的，然後在[L,R]中掃一遍，通過 sa 數組看有哪些貓的名或姓在這其中，統計答案即可。

代碼

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 1000000

using namespace std;

int sa[MAXN],height[MAXN],rank[MAXN];
int wa[MAXN],wb[MAXN],wv[MAXN],cnt[MAXN];

bool cmp(int *r,int a,int b,int c) //第一關鍵字a與b，第二關鍵字a+c,b+c
{
    return (r[a]==r[b])&&(r[a+c]==r[b+c]);
}

void SA(int *r,int n,int m) //待排序串為r，長度n-1,共有m個不同的字母
{
    int i,j,p;
    int *x=wa,*y=wb;
    for(int i=;i<m;i++) cnt[i]=;
    for(int i=;i<n;i++) cnt[x[i]=r[i]]++;
    for(int i=;i<m;i++) cnt[i]+=cnt[i-];
    for(int i=n-;i>=;i--) sa[--cnt[x[i]]]=i;
    for(j=,p=;p<n;j*=,m=p)
    {
        for(p=,i=n-j;i<n;i++) y[p++]=i;
        for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=;i<n;i++) wv[i]=x[y[i]]; //現在wv中放的是按照第二關鍵字排序後的二進制組的第一關鍵字數組
        for(i=;i<m;i++) cnt[i]=; //清空桶
        for(i=;i<n;i++) cnt[wv[i]]++;
        for(i=;i<m;i++) cnt[i]+=cnt[i-];
        for(i=n-;i>=;i--) sa[--cnt[wv[i]]]=y[i];
        swap(x,y);
        for(p=,x[sa[]]=,i=;i<n;i++) //更新新的名次數組x
            x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
    }
}

void calc(int *r,int n) //長度為n的字元串r
{
    int i,j,k=;
    for(i=;i<=n;i++) rank[sa[i]]=i;
    for(i=;i<n;height[rank[i++]]=k)
        for(k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k];k++);
}

struct Query
{
    int len,start; //該點名串起始下标為start,長度為len
}query[MAXN];

int num[MAXN];
int belong[MAXN]; //belong[i]=字元串的第i位所屬的貓的編号
int ans[MAXN]; //ans[i]=第i隻貓被點名次數
int vis[MAXN]; //vis[i]=第i隻貓所屬的點名串編号

int main()
{
    int len=,n,m;
    scanf("%d%d",&n,&m);
    int breaker=;
    for(int i=;i<=n;i++)
    {
        int l;
        scanf("%d",&l);
        for(int j=;j<=l;j++)
        {
            belong[len]=i;
            scanf("%d",&num[len++]);
        }
        num[len++]=++breaker;
        scanf("%d",&l);
        for(int j=;j<=l;j++)
        {
            belong[len]=i;
            scanf("%d",&num[len++]);
        }
        num[len++]=++breaker;
    }
    for(int i=;i<=m;i++)
    {
        scanf("%d",&query[i].len);
        query[i].start=len;
        for(int j=;j<=query[i].len;j++)
            scanf("%d",&num[len++]);
        num[len++]=++breaker;
    }
    SA(num,len,);
    calc(num,len-);
    for(int i=;i<=m;i++)
    {
        int L,R;
        L=R=rank[query[i].start];
        while(height[L]>=query[i].len) L--;
        while(height[R]>=query[i].len) R++;
        R--;
        int sum=;
        for(int j=L;j<=R;j++)
        {
            if(belong[sa[j]]) //排名為j的字尾的開頭字元是屬于某個貓的
            {
                if(vis[belong[sa[j]]]!=i) //這個字元所屬的串所屬的貓還沒被計入
                {
                    vis[belong[sa[j]]]=i;
                    sum++;
                    ans[belong[sa[j]]]++;
                }
            }
        }
        printf("%d\n",sum);
    }
    for(int i=;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');
    return ;
}