3 2 abab ab ba 1 aaa bbb 2 aaaa aa aaa
Case 1: 3 Case 2: 3 Case 3: 1
题意:一个字符串，给定若干病毒串，求不包含病毒串的字串个数。
把病毒串添加在字符串后面，中间用不同的字符隔开，然后求一个sa，height，然后从后向前扫，
去掉的包含两个部分，一个是字符串本身已经出现过的，另外一个是包含病毒串的，
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/4/10 16:33:22
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=500200;
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 str[],int sa[],int rank[],int height[],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]=str[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++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(k)k--;
j=sa[rank[i]-1];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
}
int rank[maxn],height[maxn],r[maxn],sa[maxn];
char str[maxn];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++){
int len,len1,n;
scanf("%d",&n);
scanf("%s",str);
len=len1=strlen(str);
for(int i=0;i<len;i++)r[i]=str[i];
r[len++]=127;
while(n--){
scanf("%s",str);
int cnt=strlen(str);
for(int i=0;i<cnt;i++)
r[len++]=str[i];
r[len++]=‘#‘;
}
r[len]=0;
da(r,sa,rank,height,len,200);
ll ans=0;int lcp=0;
for(int i=1;i<=len;i++){
if(sa[i]>len1)lcp=height[i];
else{
ans+=len1-sa[i]-max(height[i],lcp);
lcp=min(lcp,height[i]);
}
}
printf("Case %d: %I64d\n",t,ans);
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/23369141