Searching the String 【ZOJ - 3228】【AC自动机+last跳板优化时间】

题目链接

  这次要求的有两个，分别是0、1，代表着的是可以重叠，以及不可以重叠的遍历到该单词的次数，可以重叠的很容易，遇到的时候，就直接加上就是了，但是不可以重叠的时候呢，就需要看到该单词它和上一次的状态出现的距离差了，看一下是否比这个单词长即可。

  然后我看了一下这个，就想到需要不断的向前fail，但是由于可能fail的无效次数太多，所以就用了last跳板，但是最后发现只优化了100+ms，区别不是太大。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e5 + 7;
struct node
{
    int nex[26], fail, las, pos, id;
    void clear() { memset(nex, 0, sizeof(nex)); fail = id = pos = las = 0; }
}a[maxN<<3];
int tot, N, op[maxN], head[maxN], cnt;
char A[maxN], virus[10];
void insert(int ti)
{
    int len = (int)strlen(virus), temp = 0, _id;
    for(int i=0; i<len; i++)
    {
        _id = virus[i] - 'a';
        if(!a[temp].nex[_id])
        {
            a[++tot].clear();
            a[temp].nex[_id] = tot;
        }
        temp = a[temp].nex[_id];
    }
    a[temp].pos = len;
    if(!a[temp].id) a[temp].id = ++cnt;
    head[ti] = a[temp].id;
}
inline void build_fail()
{
    queue<int> Q;   Q.push(0);
    int tmp, son, p;
    while(!Q.empty())
    {
        tmp = Q.front();    Q.pop();
        for(int i=0; i<26; i++)
        {
            son = a[tmp].nex[i];
            if(son)
            {
                if(!tmp) a[son].fail = a[son].las = 0;
                else
                {
                    p = a[tmp].fail;
                    while(p && !a[p].nex[i]) p = a[p].fail;
                    a[son].fail = a[p].nex[i];
                    if(a[a[son].fail].id) a[son].las = a[son].fail;
                    else a[son].las = a[a[son].fail].las;
                }
                Q.push(son);
            }
        }
    }
}
int last[maxN], ans0[maxN], ans1[maxN]; //上一次出现的位置
inline void AC_auto()
{
    memset(last, -1, sizeof(last));
    int tmp = 0, len = (int)strlen(A), _id, p;
    for(int i=0; i<len; i++)
    {
        _id = A[i] - 'a';
        while(tmp && !a[tmp].nex[_id]) tmp = a[tmp].fail;
        tmp = a[tmp].nex[_id];
        if(!tmp) continue;
        p = tmp;
        while(p)
        {
            if(a[p].pos)
            {
                ans0[a[p].id]++;
                if(i - last[a[p].id] >= a[p].pos) { ans1[a[p].id]++; last[a[p].id] = i; }
            }
            p = a[p].las;
        }
    }
}
inline void init()
{
    tot = cnt = 0;
    a[0].clear();
    memset(ans0, 0, sizeof(ans0));
    memset(ans1, 0, sizeof(ans1));
}
int main()
{
    int Cas = 0;
    while(scanf("%s", A)!=EOF)
    {
        scanf("%d", &N);
        init();
        for(int i=1; i<=N; i++) { scanf("%d%s", &op[i], virus); insert(i); }
        printf("Case %d\n", ++Cas);
        build_fail();
        AC_auto();
        for(int i=1; i<=N; i++)
        {
            if(op[i]) printf("%d\n", ans1[head[i]]);
            else printf("%d\n", ans0[head[i]]);
        }
        printf("\n");
    }
    return 0;
}