# SPOJ 7258. Lexicographical Substring Search

http://vjudge.net/problem/viewProblem.action?id=28015

### Analysis:

http://vjudge.net/problem/viewSource.action?id=1577464

DP 出每個狀態出發可以識別多少子串。之後在 SAM 上，逐個字元嘗試。
。。。這種方法時間複雜度較差（依賴於子串長度）、想要通過此題需要常數優化和一定運氣。。。
http://vjudge.net/problem/viewSource.action?id=2604504

# Codechef April Challenge 2012. Substrings on a Tree

### Analysis:

```    int Ext(int c, int tail){
int u = tail, uu = new_node(); len[uu] = len[u] + 1;
while (u && !v) v = uu, u = p;
if (!u && !v) v = uu, pp = 0;
else{
if (len[v] == len[u] + 1) pp = v;
else{
int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
par[_v] = pp = vv; while (v == _v) v = vv, u = p;
}
}
return uu;
}
```

```    void Init(){

RD(n, q); RS(s+1); n = strlen(s+1); REP_1(i, n) s[i] -= 'a';

//RST(hd);
FOR_C(i, 2, n<<1){
RD(aa, bb);
suc[i] = hd[aa], hd[aa] = i++;
suc[i] = hd[aa], hd[aa] = i;
}

tot = 0; queue<int> Q; Q.push(1);
GtoM[1] = Ext(s[1], new_node());

while(SZ(Q)){
int u = Q.front(); Q.pop();
REP_G(i, u) if (!GtoM[v]){
GtoM[v] = Ext(s[v], GtoM[u]);
Q.push(v);
}
}
}
```

Select 的過程參照 SPOJ SUBLEX 即可。

http://www.codechef.com/viewsolution/4511141