http://www.lydsy.com/JudgeOnline/problem.php?id=2434

思路:建立fail树，并找出dfs序，那剩下要做的就是每次找到一个串的位置，然后询问它的区间里面有多少我当前串的节点，具体做法见代码。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           struct edge{ int to,next,id;}que[500005];int fail[500005],sz,ch[500005][26],root,num,hw,low[500005],dfn[500005];char s[500005];int pos[500005],id,fi[500005],first[500005],next[500005],tot,go[500005];int fa[500005],ans[500005],V[1000005],n,m;void insert(int x,int y){ tot++; go[tot]=y; next[tot]=first[x]; first[x]=tot;}void add(int x,int v){ for (int i=x;i<=hw;i+=(i)&(-i)){ V[i]+=v; }}int query(int x){ int res=0; for (int i=x;i;i-=(i)&(-i)){ res+=V[i]; } return res;}void build(){ int now=1;sz=1; for (int i=0;i
           

Q; for (int i=0;i<26;i++) if (!ch[root][i]) ch[root][i]=root; else if (ch[root][i]){ fail[ch[root][i]]=root; Q.push(ch[root][i]); } while (!Q.empty()){ int now=Q.front();Q.pop(); for (int i=0;i<26;i++) if (!ch[now][i]){ ch[now][i]=ch[fail[now]][i]; }else{ fail[ch[now][i]]=ch[fail[now]][i]; Q.push(ch[now][i]); } } }void dfs(int x){ dfn[x]=++hw; for (int i=first[x];i;i=next[i]){ int pur=go[i]; dfs(pur); } low[x]=++hw;}void solve(){ add(dfn[1],1);//root节点也算上 int sx=0,now=1; for (int i=0;i