POJ 1625 自动机

本文主要是介绍POJ 1625 自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出包含n个可见字符的字符集，以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串，求长为m且不包含上述p个字符串的字符串有多少个。

g++提交

int    mat[108][108] ;
int    matn ;
int    N  ;
map<char ,int> to ;
//AC
const  int  maxm = 108 ;
const  int  kind = 256 ;
int    next[maxm][kind] ;
int    fail[maxm] ;
int    id[maxm] ;struct AC{int root , n ;int newnode(){id[n] = 0 ;for(int i = 0 ; i < kind ; i++) next[n][i] = -1 ;return n++ ;}void Init(){n = 0 ;root = newnode() ;}void Insert(char *s){int now = root  , k ;while(*s){k = to[*s] ;if(next[now][k] == -1)next[now][k] = newnode() ;now = next[now][k] ;s++ ;}id[now] = 1 ;}void  makeAC(){queue<int> q ;fail[root] = root ;int now , i ;for(i = 0 ; i < kind ; i++){if(next[root][i] == -1)next[root][i] = root ;else{fail[next[root][i]] = root ;q.push(next[root][i]) ;}}while(! q.empty()){now = q.front() ; q.pop() ;if(id[fail[now]]) id[now] = 1 ;for(i = 0  ; i < kind ; i++){if(next[now][i] == -1)next[now][i] = next[fail[now]][i] ;else{fail[next[now][i]] = next[fail[now]][i] ;q.push(next[now][i]) ;}}}}void  getMat(){matn = n ;memset(mat , 0 , sizeof(mat)) ;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < N ; j++){if(id[next[i][j]] == 0)mat[i][next[i][j]]++ ;}}}
}ac ;//EndAC
const int maxn = 9999 ; // 每位储存4位
const int dig = 4 ;
class BigNum{public  :int  a[7150] ;int  len ;BigNum(){len = 1 ; memset(a , 0 , sizeof(a)) ;}BigNum(const int) ;BigNum(const char*) ;BigNum operator *(const BigNum &) const ;BigNum operator +(const BigNum &) const ;friend ostream& operator <<(ostream &out , const BigNum&T) ;
};BigNum::BigNum(const int T){int t = T ;len = 0 ;  memset(a , 0 , sizeof(a)) ;while(t > maxn){a[len++] = t - t/(maxn+1)*(maxn+1) ;t = t/(maxn+1) ;}a[len++] = t ;
}BigNum::BigNum(const char* s){memset(a , 0 , sizeof(a)) ;int t , i , j , k , id = 0 , l = strlen(s) ;len = l/dig ;if(l%dig) len++ ;for(i = l-1 ; i >= 0 ; i -= dig){t = 0 ;k = max(0  , i - dig + 1);for(j = k ; j <= i ; j++)  t = t*10 + s[j] - '0' ;a[id++] = t ;}
}ostream& operator <<(ostream &out , const BigNum&T){printf("%d" , T.a[T.len-1]) ;for(int i = T.len-2 ; i >= 0 ; i--)  printf("%04d" ,T.a[i]) ;return out ;
}BigNum BigNum::operator*(const BigNum &T) const{BigNum s ;int i , j , up  , t ;for(i = 0 ; i < len ; i++){up = 0 ;for(j = 0 ; j < T.len ; j++){t = a[i]*T.a[j] + s.a[i+j] + up ;if(t > maxn){s.a[i+j] = t - t/(maxn+1)*(maxn+1) ;up = t/(maxn+1) ;}else{up = 0 ;s.a[i+j] = t ;}}if(up != 0) s.a[i+j] = up ;}s.len = len + T.len ;while(s.a[s.len-1] == 0 && s.len>1) s.len-- ;return s ;
}BigNum BigNum::operator + (const BigNum &T) const{BigNum s ;s.len = max(len , T.len) ;for(int i = 0 ; i < s.len ; i++){s.a[i] += a[i] + T.a[i] ;if(s.a[i] > maxn){s.a[i+1]++ ;s.a[i] %= (maxn+1) ;}}if(s.a[s.len]!=0) s.len++ ;return s ;
}char  str[58] ;
BigNum dp[2][108] ;int  main(){int i , m , p , j  , k ;while(scanf("%d%d%d",&N ,&m ,&p) != EOF){scanf("%s" , str) ;to.clear() ;for(i = 0 ; i < N ; i++) to[str[i]] = i ;ac.Init() ;while(p--){scanf("%s" , str) ;ac.Insert(str) ;}ac.makeAC() ;ac.getMat() ;int now = 0 ;dp[now][0] = 1 ;for(i = 1 ; i < matn ;i++)dp[now][i] = BigNum(0) ;for(i = 0 ; i < m ; i++){now ^= 1 ;for(j = 0 ; j < matn ; j++)dp[now][j] = BigNum(0) ;for(j = 0 ; j < matn ; j++){for(k = 0 ; k < matn ; k++){if(mat[j][k] > 0)dp[now][k] = dp[now][k] + dp[now^1][j] * BigNum(mat[j][k]) ;}}}BigNum sum = BigNum(0) ;for(i = 0 ; i < matn ; i++)sum = sum + dp[now][i]  ;cout<< sum <<endl ;}return 0 ;
}

这篇关于POJ 1625 自动机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---