# 【日常小测】最长公共前缀

### 题目大意 ### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int c = 0) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}

class Suffix_Automaton{
int cnt=1,ch[N],fail[N],vis[N],dep[N],sum[N];
int tot,arr[N],que[N],len[N],fa[N],_hash[N];
vector<int> G[N]; LL ans_tmp;
public:
inline int insert(int t, int cc) {
if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc];
int tail = ++cnt; len[tail] = len[t] + 1;
while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t];
if (!t) fail[tail] = 1;
else {
if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc];
else {
int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1;
memcpy(ch[nw], ch[w], sizeof(ch[nw]));
fail[nw] = fail[w]; fail[w] = fail[tail] = nw;
for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw;
}
} return tail;
}
inline void Build_Fail_Tree() {
dfs(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=cnt;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
}
inline LL solve(int nn) {
for (int i=1;i<=nn;i++) arr[i] = pos[read()];
sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];});
for (int i=1;i<=nn;i++) _hash[i] = arr[i];
int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1;
for (int i=1;i<=nn;i++) sum[i] = 0;
for (int i=1,j=1;i<=mm;i++) {
while (arr[j] != _hash[i]) j++;
sum[j]++;
}
que[tot=1] = 1; int MX = 1;
for (int i=1,lca;i<=nn;i++) {
vis[arr[i]] = sum[i];
lca = LCA(que[tot], arr[i]);
while (dep[que[tot]] > dep[lca]) {
if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]);
else G[lca].push_back(que[tot]);
--tot;
}
if (que[tot] != lca) que[++tot] = lca;
if (arr[i] != que[tot]) que[++tot] = arr[i];
MX = max(MX, tot);
}
while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot;
ans_tmp = 0;
Get_Ans(1);
return ans_tmp;
}
private:
void dfs(int w, int f) {
static int id_count = 0;
id[w] = ++id_count;
fa[w] = f; dep[w] = dep[f] + 1;
if (to[i] != f) {
dfs(to[i], w);
}
}
}
int Get_Ans(int w) {
int ret = vis[w];
if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w];
for (int i=G[w].size()-1,tmp;~i;i--) {
tmp = Get_Ans(G[w][i]);
ans_tmp += (LL)tmp * ret * len[w];
ret += tmp;
}
vis[w] = 0;
G[w].clear();
return ret;
}
inline int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
if (a == b) return a;
for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
return fa[a];
}
}SAM;

void DFS(int w, int f, int t) {
pos[w] = t;
if (to[i] != f) {
int nt = SAM.insert(t, col[i]);
DFS(to[i], w, nt);
}
}
}

int main() {
for (int i=1,u,v;i<n;i++) {
scanf("%s",pat+1);
}
DFS(1, 1, 1);
SAM.Build_Fail_Tree();
return 0;
}


## 12 thoughts to “【日常小测】最长公共前缀”

1. tinyurl.com说道：

Everyone loves what you guys are up too. Such clever work
and reporting! Keep up the excellent works guys I’ve incorporated you guys to my own blogroll.

2. tinyurl.com说道：

I’m not sure where you’re getting your info, but great topic.
I needs to spend some time learning more or understanding
more. Thanks for magnificent information I was looking for this info for my mission.

3. where coconut oil说道：

I’ll bookmark your blog and check again here
regularly. I am quite sure I will learn many new stuff right here!
Good luck for the next!

4. plenty of fish dating site说道：

I was pretty pleased to uncover this site.
I wanted to thank you for your time for this particularly wonderful read!!
I definitely loved every bit of it and I have
you saved as a favorite to see new things on your site.

5. quest bars cheap说道：

of course like your web site but you need to test the spelling on several of your posts.
A number of them are rife with spelling issues and I in finding
it very bothersome to inform the truth then again I will definitely come
back again.

6. quest bars cheap说道：

I’ve read a few just right stuff here. Definitely
price bookmarking for revisiting. I wonder how much attempt you place to
create such a great informative site.

7. quest bars cheap coupon twitter说道：

Thanks for sharing such a nice thinking, paragraph is nice, thats why

8. ps4 games说道：

Hi! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions?

9. ps4 games说道：

It’s awesome in favor of me to have a web site, which is
useful in favor of my experience. thanks admin

10. ps4 games说道：

This is a topic which is near to my heart… Cheers! Exactly where
11. ps4 games说道：
12. coconut oil说道：