学步园

最近一直在搞字符串匹配的问题，搞到AC自动机，就去找了几道题练习一下，于是就找到了ZOJ3228。

一开始看是想将所有的子串建一棵trie，然后直接AC自动机匹配，但是发现只能匹配可重复的串，那些不可重复的串搞不定（至少对于我这个弱菜来说）。

于是上网找了下别人的想法，发现很多都不是用AC自动机做的，因为根据题意，字串的长度最多为6，那么直接拿原串中所有的长度为6的前缀串构建成一棵TRIE树就可以了。

因为原串的长度为10^5，那么最多有10^5 * 6的节点。

然后就拿子串在trie树上进行前缀的匹配。

当然要分两种情况，一种是可重复的，这种就没什么好说了。直接匹配最后输出cnt就可以了。

对于不可重复的串，我们在构建TRIE的时候，多维护一个域end,来记录该子串出现的最后位置，如果当然下一个子串的首地址，也就是数组的第一个位置已经大于该子串记录的最后位置，那么更新末位置，然后计数加一。

这里我们举个例子，例如原串是"abababa"。现在我们要构建他的不可重复串的TRIE树。我这里就举LEN = 3的时候的情况。

                                                 0123456

首先位置在012的串aba，这时我们记录他的END = 2 。

下一次遍历到该串的时候是位置234，此时他的首地址等于END，那么不计数。

再下一次遍历到的时候是位置456，此时首地址大于2，那么计数+1。

同理推到LEN = 6 的情况。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;


inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}

struct trie{
    int next[26] ;
    int overlap ;
    int unoverlap ;
    int end ;
    void init(){
        mem(next ,0) ;
        overlap = 0 ;//可重复串个数
        unoverlap = 0 ;//不可重复串
        end = -1 ;
    }
}TT[600005] ;
int num = 0 ;
void build(char *a ,int pos){
    int l = strlen(a) ;
    int p = 0 ;
    for (int i = 0 ; i < l ;i ++ ){
        int tt = a[i] - 'a' ;
        if(TT[p].next[tt] == 0){
            TT[p].next[tt] = ++ num ;
            TT[num].init() ;
        }
        p = TT[p].next[tt] ;
        TT[p].overlap ++ ;
        if(TT[p].end < pos ){
            TT[p].end = pos + i ;//记录该串最后出现的位置，当下次出现位置已经大于该位置时，则可以计数
            TT[p].unoverlap ++ ;
        }
    }
}

void search(char *a ,int pos){
    int l = strlen(a) ;
    int p = 0 ;
    for (int i = 0 ; i < l ;i ++ ){
        int tt = a[i] - 'a' ;
        if(TT[p].next[tt] == 0){
            puts("0") ;
            return ;
        }
        p = TT[p].next[tt] ;
    }
    if(pos){
        printf("%d\n",TT[p].unoverlap) ;
    }else {
        printf("%d\n",TT[p].overlap) ;
    }
    return ;
}
char str[1111111] ;
void init(){
    num = 0 ;
    TT[0].init() ;
}
char now[111] ;
int main() {
    int cas = 0 ;
    while(scanf("%s",str) != EOF){
        init() ;
        int l = strlen(str) ;
        for (int i = 0 ;i < l ; ++ i){
            int j ;
            for (j = 0 ; j < 6 && i + j < l ; j ++ ){//枚举所有长度为6的前缀串，加入TRIE树中。
                now[j] = str[i + j] ;
            }
            now[j] = 0 ;
            build(now , i) ;
        }
        int n ;
        RD(n) ;
        int op ;
        printf("Case %d\n",++ cas) ;
        while(n -- ){
            scanf("%d%s",&op ,now) ;
            search(now ,op) ;
        }
        puts("") ;
    }
    return 0 ;
}

目测还有AC自动机的做法，我去学习一下。