hdu2825
程序员文章站
2022-03-23 11:36:43
...
/*
AC自动机,增设虚拟节点,求长度为n的字符串中包含至少k个给出的关键字的字符串的个数,结果模MOD。
增设虚拟节点的目的是为了方便状态转移
*/
#include <cstdio>
#include <cstring>
using namespace std;
const int N= 105; //节点个数的最大值
const int S=26; //不同的字符 个数
const int MOD=20090717;
const int M=10; //m的最大值
const int LEN=26; //n的最大值
struct node{
node *sons[S], *fail;
int id, has; //id是节点的标号,has表示该节点拥有的关键字的组合
}nodes[N], *root;
int cnt; //cnt是树中节点的 个数
node *que[N];
int dp[LEN][1<<M][N], bits[1<<M];
int n, m, k;
void init(){
int i;
for(bits[0]=0, i=1; i <(1<<M); i++){
bits[i]=bits[i>>1]+(i&1);
}
}
void clear(){
cnt=0;
root=NULL;
}
node* newNode(){
node* ans=&nodes[cnt];
memset(ans->sons, 0, S*sizeof(node*));
ans->fail=NULL;
ans->id=cnt++;
ans->has=0;
return ans;
}
int hash(char ch){ //字符的哈希函数,根据不同的需要而定
return ch-'a';
}
void insert(node*& root, char* str, int j){
node* t=root;
int i, k;
for(i=0; str[i]; i++){
if(t->sons[k=hash(str[i])]==NULL){
t->sons[k] = newNode();
}
t=t->sons[k];
}
t->has|=(1<<j);
}
//在某些时候还需要吧root的S个儿子节点中为空赋值为root(所谓的虚拟节点,树中的 其他节点也可以
//添加类似的虚拟节点)
void getFail(node*& root){
int l, r, i;
node *t;
l=r=0;
root->fail=root; //这样可以保证每个节点的fail指针都是非空的
for(que[r++]=root; l!=r; ){
t=que[l++];
for(i=0; i<S; i++){
if(t->sons[i]){
que[r++]=t->sons[i];
if(t==root){
t->sons[i]->fail=t;
}else{
t->sons[i]->fail=t->fail->sons[i];
}
t->sons[i]->has|=t->sons[i]->fail->has;
}else{ //增设虚拟节点
if(t==root) t->sons[i]=t;
else t->sons[i]=t->fail->sons[i];
}
}
}
}
bool input(){
scanf("%d%d%d", &n, &m, &k);
if(n==0 && m==0 && k==0) return false;
char str[15];
int i;
clear();
root=newNode();
for(i=0; i<m; i++){
scanf("%s", str);
insert(root, str, i);
}
return true;
}
void solve(){
getFail(root);
int i, j, h, sum, g;
sum=(1<<m);
for(i=0; i<=n; i++){
for(j=0; j<sum; j++){
for(h=0; h<cnt; h++){
dp[i][j][h]=0;
}
}
}
dp[0][0][0]=1; //一般来说根节点的id都是0
for(i=0; i<n; i++){
for(j=0; j<sum; j++){
for(h=0; h<cnt; h++){
int &d1=dp[i][j][h];
if(d1==0) continue;
for(g=0; g<S; g++){
int ts=j|nodes[h].sons[g]->has;
int &d2=dp[i+1][ts][nodes[h].sons[g]->id];
d2+=d1;
if(d2>MOD){
d2 -= MOD;
}
}
}
}
}
int ans=0;
for(j=0; j<sum; j++){
if(bits[j]<k) continue;
for(h=0; h<cnt; h++){
ans+=dp[n][j][h];
if(ans>MOD){
ans-=MOD;
}
}
}
printf("%d\n", ans);
}
int main(){
//freopen("in.txt", "r", stdin);
init();
while(input()) solve();
return 0;
}
上一篇: Leetcode 第30场双周赛