把各种子串hash成不同的数值存在表里，[ i ][ j ]表示从i开始到j结束的子串的hash值。然后就是求某个点到左下点所形成的矩形里不同的数有多少。。判重后DP一遍就可以了。。。。

普通的hash+map居然会MLE，没办法改成字典树hash了。。。。。

Reincarnation

2
bbaba
5
3 4
2 2
2 5
2 4
1 4
baaba
5
3 3
3 4
1 4
3 5
5 5

3
1
7
5
8
1
3
8
5
1
Hint
      I won‘t do anything against hash because I am nice.Of course this problem has a solution that don‘t rely on hash.
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int M=2013325;
const int N=2013;

int c[N][N],last[M],K[M],n,Q;
char str[N];

struct Edge
{
    int to,next;
    char c;
}E[M];

int Adj[M],Size,cnt,num;

int Add_Char(char a,int& x)
{
    bool flag=false;
    for(int i=Adj[x];~i;i=E[i].next)
    {
        if(E[i].c==a)
        {
            x=E[i].to;
            flag=true;
            break;
        }
    }
    if(flag) return K[x];

    K[cnt]=num++;
    E[Size].to=cnt;
    E[Size].c=a;
    E[Size].next=Adj[x];
    Adj[x]=Size++;
    x=cnt++;

    return K[x];
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%s",str);
    n=strlen(str);

    memset(c,0,sizeof(c));
    memset(last,-1,sizeof(last));
    memset(Adj,-1,sizeof(Adj));
    cnt=1;Size=num=0;

    for(int j=1;j<=n;j++)
    {
        for(int i=j,t=0;i>=1;i--)
        {
            int k=Add_Char(str[i-1],t);
            if(last[k]==-1)
            {
                last[k]=i;
                c[i][j]++;
            }
            else if(last[k]<i)
            {
                c[i][j]++;
                c[last[k]][j]--;
                last[k]=i;
            }
        }
    }

    for(int i=n;i>=1;i--)
    {
        for(int j=i;j<=n;j++)
        {
            c[i][j]+=c[i][j-1]+c[i+1][j]-c[i+1][j-1];
        }
    }

    scanf("%d",&Q);
    while(Q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",c[l][r]);
    }
}
    return 0;
}

HDOJ 4622 Reincarnation (hash),布布扣,bubuko.com

HDOJ 4622 Reincarnation (hash)

原文：http://blog.csdn.net/u012797220/article/details/22041709