首页 > 代码库 > BZOJ4502: 串

BZOJ4502: 串

2024-09-08 17:55:22   219人阅读

题意：给定一个由n个串组成的集合（n<=10000,len<=30），求组成不同好串的方案数。其中好串的定义为：可被分割成两个非空串且分别对应原集合中两个串（可相同）的前缀。

首先直接弄肯定不行，会算重。所以要么除掉相同方案或者找到一种不重不漏的计算方式。这里提供一种不重不漏的dp。

AC自动机上dp。我们定义dp状态dp[i][j]表示第一次失配之后我们加了i个字符，当前在j节点的方案数。

转移如下：dp[i][j]->dp[i+1][next[j][a]]其中a为我们当前枚举的转移字符，并且要满足条件：状态next[j][a]的长度要大于i。

现在来解释这样为什么能做到不重不漏。dp状态里的这个i其实并不能完全说是加了i个字符，也许说走了i步更加合适，因为我们dp完后去看对应的方案其实不一定就是在分割点后加了i个字符。我们基于的思想是这样的：我们在初始化的时候，枚举AC自动机上哪些节点没有当前枚举字符的转移，但是fail指向的又不是root，这些作为我们的第一“切割点”（待会解释为什么这里是打引号）。然后我们开始往里面丢字符，也许我们丢了之后转移到的状态对应的长度是大于我们目前加的这后面一段总长度的，但这不要紧，我们可以把多的那一部分前缀补到分割点前面去，也就是说分割点前移，所以说为什么前面要打引号，是这个原因。

举个例子，我们在前面一部分串为ABC，我们在这个C后面断开开始找第二段。此时第一“切割点”就是这个C。假如我们枚举一个D，而后缀自动机把它转移到了BCD状态上，我们可以视作将切割点迁移至了A后面，最后对应的分割方式就是A|BCD。

好，那么为什么要满足那个长度要大于i的条件呢？因为一旦小等i，就说明没有一个对应的方案可以实现，这是不存在的。

再回到本质问题上来，为什么能不重不漏。经过多番讨论，我想到一个较为准确的表述：我们发现，我们用这种分割方式，第一“分割点”一定会选择一个位置，使得实际分割点到第一分割点尽可能的长，这就使得每个串有一个唯一的划分方式，使得不重不漏。

上面说了不重，还要注意不漏。有一些串在我们初始化的时候是断不开的，对于这些串我们要特判一下，一开始就计入答案。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define N 300005
 5 
 6 inline LL read(){
 7        LL x=0,f=1; char a=getchar();
 8        while(a<‘0‘ || a>‘9‘) {if(a==‘-‘) f=-1; a=getchar();}
 9        while(a>=‘0‘ && a<=‘9‘) x=x*10+a-‘0‘,a=getchar();
10        return x*f;
11 }
12 
13 int n,cnt,next[N][26],f[N],root,lim,dep[N];
14 bool tr[N][26];
15 LL ans,dp[100][N];
16 queue<int>q;
17 
18 inline void insert(){
19     char tmp[35]; memset(tmp,0,sizeof(tmp)); scanf("%s",tmp+1);
20     int len=strlen(tmp+1),now=root;lim=max(lim,2*len);
21     for(int i=1;i<=len;i++){
22         int a=tmp[i]-‘a‘;
23         if(!next[now][a]) next[now][a]=++cnt; 
24         now=next[now][a];
25     }
26 }
27 
28 inline void getfail(){
29     for(int i=0;i<26;i++) if(next[root][i])    dep[next[root][i]]=1,q.push(next[root][i]);
30     while(!q.empty()){
31         int p=q.front(); q.pop();
32         for(int i=0;i<26;i++){
33             int v=next[p][i];
34             if(!v) {next[p][i]=next[f[p]][i];continue;}
35             tr[p][i]=1;
36             int k=f[p];
37             while(k && !next[k][i]) k=f[k]; k=next[k][i];
38             f[v]=k; dep[v]=dep[p]+1;
39             q.push(v);
40         }
41     }
42 }
43 
44 int main(){
45     n=read();
46     for(int i=1;i<=n;i++) insert(); getfail();
47     for(int i=1;i<=cnt;i++) if(f[i]!=root) ans++;
48     for(int i=1;i<=cnt;i++)
49         for(int a=0;a<26;a++)
50             if(!tr[i][a] && next[i][a]!=root) dp[1][next[i][a]]++;
51     for(int i=1;i<=lim;i++)
52         for(int j=1;j<=cnt;j++)
53         if(dp[i][j]){
54             ans+=dp[i][j];
55             for(int a=0;a<26;a++)
56                 if(tr[j][a] || dep[next[j][a]]>=i+1) dp[i+1][next[j][a]]+=dp[i][j];
57         }
58     printf("%lld\n",ans);
59     return 0;
60 }

 

BZOJ4502: 串


联系
我们