原根
最优解
考虑建立一棵字典树,一个字符串为另一个字符串的前缀,当且仅当它对应的节点是另一个节点的祖先。所以我们建立完字典树之后,标记一下每个结点作为字符串的终点几次。最后从根开始往下搜索,当搜索到一个结束位置的时候,如果这个结束位置只代表一个字符串那么就统计入答案,不然就不统计。并且搜到一个结束位置就不用往下搜了,因为下面即使搜到了结束位置也不可能是原根,当前的结束位置必然会是它的祖先。
时间复杂度和空间复杂度都是
int ch[1000005][26]; int is_over[1000005]; int dfs(int u){ if(is_over[u]){ return (is_over[u] == 1); } int ans = 0; for(int i = 0; i < 26; ++i) if(ch[u][i]) ans += dfs(ch[u][i]); return ans; } int solve(int n, vector<string> s){ int tot = 0; int rt = ++tot; memset(ch[rt], 0, sizeof ch[rt]); is_over[rt] = 0; for(int i = 0; i < n; ++i){ int p = rt; for(int j = 0; j < s[i].size(); ++j){ int x = s[i][j] - 'a'; if(!ch[p][x]) { ch[p][x] = ++tot; memset(ch[tot], 0, sizeof ch[tot]); is_over[tot] = 0; } p = ch[p][x]; } is_over[p]++; } return dfs(rt); }