后缀自动机)

发布时间:2017-2-24 11:47:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"后缀自动机)",主要涉及到后缀自动机)方面的内容,对于后缀自动机)感兴趣的同学可以参考一下。

  uva 719 - Glass Beads(后缀自动机) 分类: 后缀自动机2013-09-08 20:06 69人阅读 评论(0) 收藏 举报 后缀自动机 uva 719 - Glass Beads(后缀自动机) 题意:求循环同构的最小表示的起点。 解题思路:这题用后缀自动机来解,牛刀杀鸡啊,我只是写写模板。。构造好sam之后,按字典序,dfs遍历,当深度达到n时,就返回当前节点的val值(也就是它的len),记录为k,那么答案就是k-n+1。 [cpp] view plaincopyprint? #include<stdio.h>   #include<string.h>   #include<algorithm>   using namespace std ;      const int maxn = 1111111 ;   struct Suf_auto {       int tot , last , c[26][maxn<<1] , pre[maxn<<1] , val[maxn<<1] ;       inline void new_node ( int step ) {           int i ;           val[++tot] = step ;           for ( i = 0 ; i < 26 ; i ++ ) c[i][tot] = 0 ;           pre[tot] = 0 ;       }       void build ( char *s , int len ) {           int i , j , k ;           tot = 0 ;           new_node ( 0 ) ;           last = 1 ;           for ( i = 0 ; i < len ; i ++ ) {               new_node ( val[last] + 1 ) ;               int np = tot ;               k = s[i] - 'a' ;               while ( !c[k][last] && last ) c[k][last] = tot , last = pre[last] ;               if ( !last ) pre[tot] = 1 ;               else {                   int q = c[k][last] ;                   if ( val[q] != val[last] + 1 ) {                       new_node ( val[last] + 1 ) ;                       for ( j = 0 ; j < 26 ; j ++ ) c[j][tot] = c[j][q] ;                       pre[tot] = pre[q] ;                       pre[q] = pre[np] = tot ;                       while ( c[k][last] == q && last )                            c[k][last] = tot , last = pre[last] ;                   }                   else pre[tot] = q ;               }               last = np ;           }       }       int dfs ( int rt , int step , int n ) {           if ( step == n ) return val[rt] ;           int i ;           for ( i = 0 ; i < 26 ; i ++ )               if ( c[i][rt] ) {                   int k = dfs ( c[i][rt] , step + 1 , n ) ;                   if ( k ) return k ;               }           return 0 ;       }       void solve ( int n ) {           int i , j , k ;           printf ( "%d\n" , dfs ( 1 , 0 , n ) - n + 1 ) ;       }       void travel ( int rt ) {           int i ;           printf ( "val[%d] = %d\n" , rt , val[rt] ) ;           for ( i = 0 ; i < 26 ; i ++ )               if ( c[i][rt] ) travel ( c[i][rt] ) ;       }   } suf;      char s[111111] ;   int main () {       int cas , len , i , j ;       scanf ( "%d" , &cas ) ;       while ( cas -- ) {           scanf ( "%s" , s ) ;           len = strlen ( s ) ;           int n = len ;           for ( i = 0 ; i < n ; i ++ ) s[len++] = s[i] ;           s[len] = 0 ;           suf.build ( s , len ) ;       //  suf.travel ( 1 ) ;           suf.solve ( n ) ;       }   }  

上一篇:hdu 4707 pet acm
下一篇:HDU 4708

相关文章

关键词: 后缀自动机)

相关评论