学步园

题意：题目给定一颗二叉树，前序遍历二叉树的时候产生一个01的欧拉序列，输出某个01串在此序列中出现了几次。

总结：真是弱。。。。我居然模拟查找二叉树的生成，这可能退化到N^2。。。，引用了一个结论：

http://www.cppblog.com/hanfei19910905/archive/2012/07/02/181144.html

nlogn的算法生成静态二叉树，mark一下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#pragma comment(linker, "/STACK:36777216")
using namespace std;

const int N = 600050;

char s[N << 1],p[N];
int next[N],n,a[N],idx,lenp,lens,tot;
int left[N],right[N],stack[N],top;
bool vis[N];
set<int> myset;

void init(int key){
    myset.clear();
    top = 0;
    for(int i = 1;i <= n;i ++)
        left[i] = right[i] = -1;
    myset.insert(key);
}

void insert(int key){
    // printf("key:%d  ",key);
    myset.insert(key);
    set<int> ::iterator less,more;
    more = less = myset.lower_bound(key);
    if(less != myset.begin()){
        less --;
        if(right[*less] == -1) {right[*less] = key;
            // printf("less:%d\n",*less);
            return ;
        }
    }
    more ++;
    if(more != myset.end() && left[*more] == -1) left[*more] = key;
    // printf("more:%d\n",*more);
}

void setNext(){
    int j = 0 , k = -1;
    next[j] = k;
    while(j < lenp){
        if(k == -1 || p[j] == p[k]){
            if(p[j + 1] == p[k + 1]) next[++ j] = next[++ k];
            else next[++ j] = ++k;
        }
        else k = next[k];
    }
}

void dfs(int cur){
    memset(vis,false,sizeof(vis));
    top = 0;
    stack[++ top] = cur;
    while(!vis[cur]){
        int u = stack[top];
        s[lens ++] = '0' + (u & 1);
        int v = left[u];
        if(v != -1 && !vis[v]) {stack[++ top] = v;continue;}
        v = right[u];
        if(v != -1 && !vis[v]) {stack[++ top] = v; continue;}
        top --;
        vis[u] = 1;
    }
}

int kmp(){
    int i = 0,j = 0;
    int Count = 0;
    while(i < lens){
        if(j == -1 || s[i] == p[j]){
            i ++,j ++;
            if(j == lenp) Count ++;
        }
        else j = next[j];
    }
    return Count;
}

int main(){
    // freopen("input.txt","r",stdin);
    int cas;
    scanf("%d",&cas);
    for(int t = 1;t <= cas;t ++){
        scanf("%d",&n);
        for(int i = 0;i < n;i ++)
            scanf("%d",&a[i]);
        scanf("%s",p);
        init(a[0]);
        for(int i = 1;i < n;i ++)
            insert(a[i]);
        // printf("LLLL:%d\n",left[5]);
        lens = 0;
        dfs(a[0]);
        s[lens] = '\0';
        lenp = strlen(p);
        // printf("s:%s\n",s);
        setNext();
        int ans = kmp();
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}