[hdoj4622]Reincarnation 字符串hash+dp

Reincarnation

题意

区间查询不同字符串的数量。

题解

字符串hash+dp思想

我们从$1-len$枚举子串的长度，如果该区间内子串就加1。由于可能会有重复所以记录长度为$x$的子串最后一次出现的$L$。如果子串出现过那么$dp[L][R]-1$。

定义$dp[l][r]$为在$[l,r]$区间内不同子串的数量那么可以得到递推公式

1. $dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]$

相当于把一个区间拆成三部分，$[l+1][r],[l][r-1],[l+1][r-1]$，这三个区间合并就是前两个集合个数相加之后减掉这两个集合并的部分元素的个数。

妙啊！

之后在预处理枚举出每一种长度的子串，从1循环到Len，如果发生重复那么可以将之前出现的+1操作的$L$到现在操作的$R$减少一个，那么这个区间的不同子串的个数就减少了一个。而且由于是递推的所以所有$[1,2,3,4,5]-L,R$都会减少1.

由于$n\leq 2000$所以可以使用$O(n^2)$的做法。

主要是dp要想明白，如果一旦确定了递推情况，就不用管细枝末节的东西了，直接在区间上减少就可以了，使得每次dp都是正确的。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e3+10;
typedef unsigned long long ull;
int n;
char s[maxn];
ull base[maxn],has[maxn],pos[maxn];
ull bas = 131;
const int mod = 1e5+7;
struct Hash_table{
    int head[mod+2],num;
    ull edgenum[maxn];
    int next[maxn],close[maxn];
    void init(){
        num = 0;
        memset(head,-1,sizeof(head));
    }
    int add(ull val,int id){
        int u = val % mod;
        for(int i=head[u];~i;i=next[i]){
            if(val == edgenum[i]){
                int temp = close[i]; close[i] = id;
                return temp;
            }
        }
        edgenum[num] = val;
        close[num] = id;
        next[num] = head[u];
        head[u] = num++;
        return -1;
    }
}H;
int dp[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    base[0] = 1;
    rep(i,1,maxn) base[i] = base[i-1]*bas;
    while(T--){
        scanf("%s",s+1); int len = strlen(s+1);
        memset(dp,0,sizeof(dp));
        rep(i,1,len+1) has[i] = has[i-1]*bas + s[i] - 'a' + 1;
        for(int x=1;x<=len+1;x++){
            H.init();
            for(int i=1;i+x-1<=len;i++){
                int pos = H.add(has[i+x-1]-base[x]*has[i-1],i);
                dp[i][x+i-1]++;
                if(pos != -1) dp[pos][x+i-1]--;
            }
        }
        per(i,1,len+1) rep(j,i,len+1) 
            dp[i][j] += dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
        int q;scanf("%d",&q);
        while(q--){
            int x,y;scanf("%d%d",&x,&y);
            printf("%d\n",dp[x][y]);
        }
    }

    return 0;
}