随笔-141  评论-9  文章-3  trackbacks-0

题意:n个字符组成长度为m的串,有一系列模式串pi,求不包含这些模式串的串有多少。

分析:对这些模式串构建AC自动机。

AC自动机其实就是trie树+失败指针,原理和KMP算法差不多。

失败指针的建立可以采用BFS,对于每个节点,我们可以这样处理:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到了root都没找到,那就把失败指针指向root

最开始,我们把root加入队列(root的失败指针显然指向自己),这以后我们每处理一个点,就把它的所有儿子加入队列,直到搞完。


本题中,设dp[i][j]为串的长度为i时候,到达状态j 的数量,

dp[i+1][id] = dp[i][j] + dp[i+1][id]; j是id的父节点。 此时要记得去掉复合模式串的结点。

最后就是要用高精度加法。

#include <iostream>
#include 
<algorithm>
#include 
<cstring>
#include 
<cstdlib>
#include 
<cstdio>
 
using namespace std;

const int MAXC = 50;
const int MAXN = 500;
 
template
<int LIM,int MAX> class hp{
    
public:
        
//vars
        int sect[MAX];
        
int scnt;
        
//constructors
        hp(){
            scnt
=1;
            sect[
0]=0;
        }

        
//functions
        void copy(int A){
            scnt
=0;
            
while (A){
                sect[scnt
++]=% LIM;
                A 
/=LIM;
            }

        }

        
void copy(const hp<LIM,MAX> &A)
        
{
            
for (int i=0;i<A.scnt;i++)
                sect[i]
=A.sect[i];
            scnt
=A.scnt;
        }

        
void print(){
            
int i,k;
            printf(
"%d",sect[scnt-1]);
            
for (i=scnt-2;i>=0;i--){
                k
=LIM/10;
                
while(sect[i]<k){
                    printf(
"0");
                    k
/=10;
                }

                
if (sect[i])
                    printf(
"%d",sect[i]);
            }

        }

        
void read(int LIE){
            
char A[LIM*MAX];
            
int len,i,j,k,b=0;
            scanf(
"%s",A);
            len
=strlen(A);
            k
=len % LIE;
            j
=scnt=len / LIE;
            
if (k){
                scnt
++;
                j
=scnt-1;
                sect[j]
=0;
                
for (i=0;i<k;i++){
                    sect[j]
*=10;
                    sect[j]
+=A[b++]-'0';
                }

            }

            
for (j--;j>=0;j--){
                sect[j]
=0;
                
for (i=0;i<LIE;i++){
                    sect[j]
*=10;
                    sect[j]
+=A[b++]-'0';
                }

            }

        }

        
void plus(hp<LIM,MAX> &A,int offset=0){
            
int sc=scnt > A.scnt + offset  ? scnt : A.scnt + offset;
            
int i,j,up=0;
            
for (i=0;i<sc;i++){
                j
=- offset;
                
if (j<0continue;
                
if (i>=scnt) sect[i]=0;
                
if (j>=A.scnt) A.sect[j]=0;
                sect[i]
+=A.sect[j] + up;
                up
=sect[i] / LIM;
                sect[i]
%=LIM;
            }

            scnt
=sc;
            
if (up) sect[scnt++]=up;
        }

        
//operators
        
        
void operator =(hp<LIM,MAX> A){
            copy(A);
        }

        
void operator =(int A){
            copy(A);
        }

        
void operator +=(hp<LIM,MAX> &A){
            plus(A);
        }

        hp
<LIM,MAX> operator +(hp<LIM,MAX> &A){
            hp
<LIM,MAX> C(*this);
            C.plus(A);
            
return C;
        }

}
;
 
typedef hp
<10000,50> hpnum;

struct node {
       
int  f,id;
       node 
*fail;
       node 
*next[MAXC]; 
}
;

node list[MAXN];
int nodeCnt ,idx[500] ;
node 
*root;
node 
*que[MAXN];

inline node 
*newnode() {
       node 
*ans = &list[++nodeCnt];
       ans
->= 0;
       ans
->id = nodeCnt;
       ans
->fail = NULL;
       
for(int i = 0 ; i < MAXC;i++ )
               ans
->next[i] = NULL;
       
return ans;
}

void insert(char *s) {
       node 
*= root;
       
while*s ){
              
int id = idx[ *+ 100 ];
              
if( p->next[id] == NULL ) p->next[id] = newnode();
              p 
= p->next[id];
              s
++;
       }

       p
->= 1;
}

void ac_automation() {
       
int head = 0 ,tail = 1;    
       root
->fail = NULL;
       que[head] 
= root;
       node 
*p ;
   
       
while( head < tail ) {
           p 
= que[head++];
           
forint i = 0 ; i < MAXC ; i++ ) {
                
if( p->next[i] != NULL) {
                    
if( p == root ) p->next[i]->fail = root;
                    
else {
                         node 
*tmp = p->fail;
                         
while( tmp != NULL ){
                              
if( tmp->next[i] != NULL ) {
                                     p
->next[i]->fail = tmp->next[i];
                                     
if( tmp->next[i]->== 1) p->next[i]->= 1
                                     
break;
                              }

                              tmp 
= tmp->fail; 
                         }
   
                         
if( tmp == NULL ) p->next[i]->fail = root;
                    }
 
                    que[tail
++= p->next[i];
                }

           }

       }

}


hpnum dp[MAXC
+5][505];
int  n, m;

void solve() {
     
int i , j, k; 

     dp[
0][1]=1;
     
for( i = 0 ; i < m;i++ )
       
for( j = 1 ; j<=nodeCnt; j++ )
         
for( k = 0 ; k < n ; k++ ) {
              node 
*tmp = list[j].next[k];
              
if( tmp != NULL) {
                  
int  id = list[j].next[k]->id;
                  
if( list[j].next[k]->== 0)
                      dp[i
+1][id] = dp[i][j] + dp[i+1][id] ;
              }

              
else {
                   node 
*= list[j].fail;
                   
while( p ) {
                          
if( p->next[k] != NULL ) break;
                          p 
= p->fail;
                   }

                   
if( p == NULL ) p = root;
                   
else  p = p->next[k];
                   
if( p->== 0 ) 
                       dp[i
+1][p->id] = dp[i][j] + dp[i+1][p->id];
              }

         }

     
     hpnum  ans ;
     
for( i = 1 ; i <= nodeCnt; i++ ) 
       ans 
+= dp[m][i] ;
     ans.print();
     cout
<<endl;
}


int main() {
    
int i,p;
    
while( scanf("%d%d%d",&n,&m,&p) != EOF) {
           nodeCnt 
= 0;
           root 
= newnode();
           
char   s[100];
           scanf(
"%s",s);
           
for( i = 0 ; i < strlen(s) ;i++)
                idx[ s[i] 
+ 100 ] = i;
           
for( i = 0 ;i < p ;i++ ) {
                scanf(
"%s",s);
                insert(s);
           }

           ac_automation();
           solve();
    }

    
return 0;
}

posted on 2011-03-22 22:58 小阮 阅读(538) 评论(1)  编辑 收藏 引用 所属分类: POJ

评论:
# re: pku 1625 Censored! (AC自动机, DP, 高精度加法) 2011-05-06 22:24 | cainiao
可以解释下dp公式怎么来的吗?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理