首页 > 搜索 > DFS搜索 > HDU 4787-GRE Words Revenge-DFS-[解题报告]HOJ
2015
09-18

HDU 4787-GRE Words Revenge-DFS-[解题报告]HOJ

GRE Words Revenge

问题描述 :

  Now Coach Pang is preparing for the Graduate Record Examinations as George did in 2011. At each day, Coach Pang can:
  "+w": learn a word w
  "?p": read a paragraph p, and count the number of learnt words. Formally speaking, count the number of substrings of p which is a learnt words.
  Given the records of N days, help Coach Pang to find the count. For convenience, the characters occured in the words and paragraphs are only ’0′ and ’1′.

输入:

  The first line of the input file contains an integer T, which denotes the number of test cases. T test cases follow.
  The first line of each test case contains an integer N (1 <= N <= 105), which is the number of days. Each of the following N lines contains either "+w" or "?p". Both p and w are 01-string in this problem.
  Note that the input file has been encrypted. For each string occured, let L be the result of last "?" operation. The string given to you has been shifted L times (the shifted version of string s1s2 … sk is sks1s2 … sk-1). You should decrypt the string to the original one before you process it. Note that L equals to 0 at the beginning of each test case.
  The test data guarantees that for each test case, total length of the words does not exceed 105 and total length of the paragraphs does not exceed 5 * 106.

输出:

  The first line of the input file contains an integer T, which denotes the number of test cases. T test cases follow.
  The first line of each test case contains an integer N (1 <= N <= 105), which is the number of days. Each of the following N lines contains either "+w" or "?p". Both p and w are 01-string in this problem.
  Note that the input file has been encrypted. For each string occured, let L be the result of last "?" operation. The string given to you has been shifted L times (the shifted version of string s1s2 … sk is sks1s2 … sk-1). You should decrypt the string to the original one before you process it. Note that L equals to 0 at the beginning of each test case.
  The test data guarantees that for each test case, total length of the words does not exceed 105 and total length of the paragraphs does not exceed 5 * 106.

样例输入:

2
3
+01
+01
?01001
3
+01
?010
?011

样例输出:

Case #1:
2
Case #2:
1
0

hdu 4787 GRE Words Revenge (在线AC自动机)

题意:学习英语单词,有n个操作,每次可以读入一个单词,或者询问一个文本串,查询有多少个不同的单词已读入。文本是被加密过的,加密的方法就是将文本旋转上一次询问的答案次。旋转的操作不解释了,看下题目吧。

解题:AC自动机。大致的思路是用两个自动机,一个heap,一个buf,buf限制一个容量,buf插满了之后,再把buf合并到heap上。那么怎么达到在线呢?其实就是重建自动机。对于buf,因为容量上限是有阈值的,所以重建一次buf,复杂度是这个阈值的大小,而我们插入的次数最多只有L次,因此这个总复杂度是L*sqrt(L)的。而合并,其实也是暴力合并,把buf里的节点一个一个的往heap里面插,然后重建heap,每次合并操作的复杂度是heap的大小,但是我们只有在buf的大小超过阈值才会合并,因此总的最多只会合并sqrt(L)次。那么这里总的复杂度是L*sqrt
(L)的。再就是询问,询问就把读进来的串在heap和buf上各跑一遍,然后和加起来就好了。当然了,这些只是大致的思路,具体细节还是有点麻烦的。

代码:

#pragma comment( linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#define ll __int64
using namespace std ;

const int maxn = 511111 ;

struct AC_auto {
    int tot , c[2][maxn] , fail[maxn] , val[maxn] ;
    int cnt[maxn] , tri[2][maxn] ;
    queue<int> q ;
    inline int new_node () {
        int i ;
        for ( i = 0 ; i < 2 ; i ++ )
            c[i][tot] = tri[i][tot] = 0 ;
        val[tot] = cnt[tot] = 0 ;
        return tot ++ ;
    }
    void init () {
        tot = 0 ;
        new_node () ;
    }
    int search ( char *s ) {
        int i , now = 0 ;
        for ( i = 0 ; s[i] ; i ++ ) {
            int k = s[i] - '0' ;
            now = tri[k][now] ;
            if ( !now ) return 0 ;
        }
        if ( cnt[now] ) return 1 ;
        return 0 ;
    }
    void insert ( char *s ) {
        int now = 0 , i , j ;
        for ( ; *s ; s ++ ) {
            int k = *s - '0' ;
            if ( !tri[k][now] ) tri[k][now] = new_node () ;
            now = tri[k][now] ;
        }
        cnt[now] = 1 ;
    }
    void get_fail () {
        int u = 0 , e , i , j ;
        for ( i = 0 ; i < tot ; i ++ ) fail[i] = 0 ;
        for ( i = 0 ; i < 2 ; i ++ )
            if ( tri[i][u] ) {
                q.push ( tri[i][u] ) ;
                c[i][u] = tri[i][u] ;
                val[c[i][u]] = cnt[c[i][u]] ;
            }
        while ( !q.empty () ) {
            int u = q.front () ;
            q.pop () ;
            for ( i = 0 ; i < 2 ; i ++ ) {
                if ( tri[i][u] ) {
                    c[i][u] = tri[i][u] ;
                    e = c[i][u] ;
                    j = fail[u] ;
                    fail[e] = c[i][j] ;
                    q.push ( e ) ;
                    val[e] = val[fail[e]] + cnt[e] ;
                }
                else c[i][u] = c[i][fail[u]] ;
            }

        }
    }
    ll find ( char *s , int len ) {
        int now = 0 ;
        ll ans = 0 ;
        int i ;
        for ( i = 1 ; i <= len ; i ++ ) {
            int k = s[i] - '0' ;
            now = c[k][now] ;
            ans += val[now] ;
        }
        return ans ;
    }
} heap , buf ;

void init () {
    heap.init () ;
    buf.init () ;
}
void dfs ( int u1 , int u2 ) {
    int i ;
    for ( i = 0 ; i < 2 ; i ++ ) {
        if ( buf.tri[i][u2] ) {
            int e2 = buf.tri[i][u2] ;
            if ( !heap.tri[i][u1] ) heap.tri[i][u1] = heap.new_node () ;
            int e1 = heap.tri[i][u1] ;
            heap.cnt[e1] |= buf.cnt[e2] ;
            dfs ( e1 , e2 ) ;
        }
    }
}

void join () {
    dfs ( 0 , 0 ) ;
    buf.init () ;
    heap.get_fail () ;
}

char s[7654321] ;
char s1[7654321] ;
int main () {
    int cas , ca = 0 , i , j ;
    scanf ( "%d" , &cas ) ;
    while ( cas -- ) {
        printf ( "Case #%d:\n" , ++ ca ) ;
        int n ; ll last = 0 ;
        init () ;
        scanf ( "%d" , &n ) ;
        while ( n -- ) {
            scanf ( "%s" , s1 ) ;
            int len = strlen ( s1 + 1 ) ;
            s[0] = s1[0] ;
            for ( i = 0 ; i < len ; i ++ ){
                s[i+1] = s1[1+(i+last%len+len)%len] ;
            }
            s[len+1] = 0 ;
            if ( s[0] == '+' ) {
                i = buf.search ( s + 1 ) ;
                j = heap.search ( s + 1 ) ;
                if ( i || j ) continue ;
                buf.insert ( s + 1 ) ;
                buf.get_fail () ;
                if ( buf.tot > 2000 ) join () ;
            }
            else {
                last = buf.find ( s , len ) + heap.find ( s , len ) ;
                printf ( "%I64d\n" , last ) ;
            }
        }
    }
    return 0 ;
}
/*
2
10
+01
+110
?010
+110
+00
+0
?001001
?001001
+110110
?1101001101

2
10
+01
+110
+110
+00
+0
?001001

1
20
+101001011
?110100
+11010100
?0011001101
+111011
?00010011
+0111010110
+0000101
+0
+11000
?1
+1010101
+0001
+0110
+0111101111
?1100
+0111
+1001
?0110111011
?1010010100

1
10
+00
?010110100
+0100000100
+111
+000000
?0000110
+110
+00
+0011
?101001

1
20
+0
+1000100
+01
+0
?1110010011

*/

参考:http://blog.csdn.net/no__stop/article/details/16823479