Description
Long time ago, there was a strange kingdom. Peoples ofdifferent religions, different cultures used to live there. But as they weredifferent, their names were also different. So, in schools, offices, it wasquite tough to call someone using his/her name, because some names were toohard to be pronounced by persons from different culture.
So, the king made a plan. He took a string S and twointegers p and q and made a rule that names of the babies shouldbe a substring ofS, and the length should be between p and q(inclusive).
Now you are given S, p and q you haveto find the number of distinct names that can be made.
Input
Input starts with an integer T (≤ 100),denoting the number of test cases.
Each case starts with a line containing a string S.The length ofS will be between 2 and 10000 (inclusive)andS contains lowercase English letters only. The next line containstwo integerp and q (1 ≤ p ≤ q ≤ length(S)).
Output
For each case, print the case number and the number ofdistinct names that can be made.
Sample Input
1
abcdef
2 5
Sample Output
Case 1: 14
Hint
题意：给定一个字符串，给定长度a和b，求长度在a，b之间的不同子串的个数。
思路；首先后缀数组预处理，然后枚举后缀，以及可能产生的前缀个数，可以分成两部分算，不大于a-1的子串的个数，不大于b的子串的个数，两者做差就得到了答案，
中间的范围限制纠结了好久。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-2 10:05:51
File Name :1.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=40000;
int str[maxn];
char ss[maxn];
int sa[maxn],height[maxn],t[maxn],t2[maxn],c[maxn],rank[maxn];
void da(int *str,int n,int m)
{
int i,j,k,p,*x=t,*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(k=1;k<=n;k<<=1)
{
p=0;
for(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++)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]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n)break;
m=p;
}
}
void calheight(int *s,int n)
{
int i,j,k=0;
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(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
// cout<<"sa:";for(i=0;i<=n;i++)cout<<sa[i]<<" ";cout<<endl;
// cout<<"rank:";for(i=0;i<=n;i++)cout<<rank[i]<<" ";cout<<endl;
// cout<<"height:";for(i=0;i<=n;i++)cout<<height[i]<<" ";cout<<endl;
}
int cal(int len,int x)
{
int t=0,k,i,j,ans=0;
for(i=1;i<=len;i++)
{
t=min(t,n-sa[i]);
ans=ans+min(x,len-sa[i])-t;
t=min(x,len-sa[i]);
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T,t;
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%s",ss);
int a,b;
scanf("%d%d",&a,&b);
int len=strlen(ss);
for(int i=0;i<len;i++)str[i]=ss[i];
str[len]=0;
da(str,len+1,300);
calheight(str,len);
int ans=0;
printf("Case %d: %d\n",t,cal(len,b)-cal(len,a-1));
}
return 0;
}