Learn Tarjan the hard way

写在前面的前面 这是一篇不严格的搬砖文。为了不引起不必要的误解,本文中描述算法的具体记号与Tarjan原文保持一致。注意:本文中部分引理和原文证明方法略有区别。 约定与记号 \(G=(\vartheta,\varepsilon )\)为有向图 路径\(p:v\overset{*}{\Rightarrow}w\)是从\(v\)到\(w\)的一条有向简单路径(这里简单路径指顶点序列中每个点都是不同的) 由\(G\)通过dfs产生的生成树记为\(T\) \((v,w)\)是\(T\)上的一条边记为\(v\rightarrow w\) 在\(T\)上有一条从\(v\)到\(w\)的路径记为\(v\overset{*}{\rightarrow}w\) \(T_{v}\)是以\(v\)为根的\(T\)的包含\(v\)的所有子孙的子树(当然也包括\(v\)) 本文中所有提到的点的标号都是对应点的dfs序     Read more
tigertang's avatar
tigertang Sep 13, 2017

KMP是什么?

Prelude prefix[S][l]是\(S\)串的长度为\(l\)的前缀 suffix[S][l]是\(S\)串的长度为\(l\)的后缀 孔乙己:你知道next array的四种写法吗? next[i]表示什么? \(nx[i]=max(l)\),其中\(l\)满足\(prefix[S][l]=suffix[prefix[S][i]][l]\)并且\(l<i\) 那怎么写呢?容我三思…… 不如先从网上抄个板子一套,反正题目过了就行QAQ     Read more
tigertang's avatar
tigertang Sep 05, 2017