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?

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'.

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

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

Case 1: 3
Case 2: 3
Case 3: 1

2012 ACM/ICPC Asia Regional Hangzhou Online

liuyiding

主要卡在如何计算含有分隔符的不同字串个数！！！！

以后再看：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define rep1(i,s,e) for(int i = (s);i<(e);++i)
#define rep2(i,s,e) for(int i = (s);i<=(e);++i)
#define maxn 310000
#define INF 1000000000
//using namespace std;

char in[maxn];
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int sa[maxn];
int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(const int *r,int *sa,int n,int m)//注意此处的char*r有时可以改成int* r
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++)
        ws[i]=0;
    for(i=0;i<n;i++)
        ws[x[i]=r[i]]++;
    for(i=1;i<m;i++)
        ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)
        sa[--ws[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,m=p)
    {
        for(p=0,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<n;i++)
            wv[i]=x[y[i]];
        for(i=0;i<m;i++)
            ws[i]=0;
        for(i=0;i<n;i++)
            ws[wv[i]]++;
        for(i=1;i<m;i++)
            ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--)
            sa[--ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return ;
}
int rank[maxn],height[maxn];
void calheight(const int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1;i<=n;i++)
        rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
    return ;
}

int ab[maxn];
int b[maxn];
int length[maxn];//the length of each previous string

int main()
{
    freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    int kcase = 1;
    while(t--)
    {
        int n;
        int cnt = 0;
        int c = 0;
        scanf("%d",&n);
        scanf("%s",in);
        int len = strlen(in);
        length[0] = len;
        int num = 26;
        int num1 = 26;
        for(int i = 0;i<len;++i)
        ab[cnt++] = in[i] - 'a' + 1;

        for(int i = 0;i<n;++i)
        {
            ab[cnt++] = num++;
            scanf("%s",in);
            len = strlen(in);
            length[i+1] = len;
            for(int j = 0;j<len;++j)
            {
                ab[cnt++] = in[j] - 'a' + 1;
                b[c++] = in[j] - 'a' + 1;
            }
            b[c++] = num1++;
        }
        ab[cnt] = 0;
        b[c] = 0;
        da(ab,sa,cnt+1,num);
        calheight(ab,sa,cnt);
        //cal ab
        long long sumab = 0;
        long long sumb = 0;

        for(int i = 1;i<=cnt;++i)
        sumab += cnt - sa[i]- height[i];

        //cnt--;
        int temp = cnt;
        for(int i = 0;i<n;++i)
        {
            temp -= length[i];
            sumab -= (length[i]+1)*temp;
            temp--;
        }

        da(b,sa,c+1,num1);
        calheight(b,sa,c);

        for(int i = 1;i<=c;++i)
        sumb += c - sa[i]- height[i];
        printf("%d\n",sumb);
        //c--;
        temp = c;
        for(int i = 1;i<n;++i)
        {
            temp -= length[i];
            sumb -= (length[i]+1)*temp;
            temp--;
        }
        printf("Case %d: %I64d\n",kcase++,sumab - sumb);

    }
    return 0;
}