当前位置：首页 > news >正文

【字符串】AC自动机+dp

news 来源：原创 2024/9/21 12:46:52

关于cnt

只有这一种

标记危险 cnt[p]=1 cnt[p]|=cnt[ne[p]]

记录个数cnt[p]++; cnt[p]+=cnt[ne[p]]

P3041 [USACO12JAN] Video Game G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
using namespace std;
#include<cstring>
const int M=1010;
const int NODE=15*20+10;
int f[M][NODE];int ne[NODE];int cnt[NODE];
int tr[NODE][3];int idx=0;
int get(char c){
if(c=='A')return 0;
if(c=='B')return 1;
if(c=='C')return 2;
}void insertt(string str){
int p=0;
for(int i=0;str[i];i++){int u=get(str[i]);if(!tr[p][u])tr[p][u]=++idx;p=tr[p][u];
}
cnt[p]++;}void bui(){int q[NODE];
int hh=0;int tt=-1;
for(int i=0;i<3;i++)if(tr[0][i])q[++tt]=tr[0][i];while(hh<=tt){int t=q[hh++];for(int i=0;i<3;i++){int p=tr[t][i];if(!p)tr[t][i]=tr[ne[t]][i];else {ne[p]=tr[ne[t]][i];cnt[p]+=cnt[ne[p]];q[++tt]=p;}}}}int main(){int n,m;
cin>>n>>m;
while(n--){string str;cin>>str;insertt(str);
}
bui();memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=0;i<m;i++){for(int j=0;j<=idx;j++){for(int u=0;u<3;u++){int p=tr[j][u];f[i+1][p]=max(f[i+1][p],f[i][j]+cnt[p]);}}
}int ans=0;
for(int j=0;j<=idx;j++){
ans=max(ans,f[m][j]);
}
cout<<ans;}

P4052 [JSOI2007] 文本生成器 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P4052[JSOI2007]文本生成器 - 洛谷专栏 (luogu.com.cn)

写了一遍10pts

写了两遍60pts

啊原来是取模，虽然sum>bu，但是sum%mod>bu%mod不一定

#include<iostream>
using namespace std;
#define ll long long
const ll mod=1e4+7;
const int NODE=100*60+10;
int tr[NODE][26];
int ne[NODE];int cnt[NODE];
int idx=0;
ll f[110][NODE];//我们虽然不会至少匹配一个
//但一个也不匹配是基础的danvoid insertt(string str){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'A';
if(!tr[p][u])tr[p][u]=++idx;
p=tr[p][u];
}
cnt[p]++;
}void bui(){
int q[NODE];
int hh=0;int  tt=-1;
for(int i=0;i<26;i++){if(tr[0][i])q[++tt]=tr[0][i];
}
while(hh<=tt){int t=q[hh++];for(int i=0;i<26;i++){int p=tr[t][i];if(!p)tr[t][i]=tr[ne[t]][i];else  {ne[p]=tr[ne[t]][i];cnt[p]|=cnt[ne[p]];q[++tt]=p;}}
}
}ll  ksm(ll a,ll b){
ll res=1;
while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;
}
return res;}
int main(){
int n,m;
cin>>n>>m;
while(n--){string str;cin>>str;insertt(str);
}
bui();f[0][0]=1;
for(int i=0;i<m;i++){for(int j=0;j<=idx;j++){for(int u=0;u<26;u++){int p=tr[j][u];if(cnt[p])continue;f[i+1][p]=(f[i+1][p]+f[i][j])%mod;}}
}ll bu=0;
for(int j=0;j<=idx;j++){bu=(bu+f[m][j])%mod;
}ll sum=ksm(26,m);cout<<(sum-bu+mod)%mod<<endl;
}