| Id | 1957 |
| Title | MagicStar |
| Tags | strings hacking brute force |
| Brief solution | 本题需要计算不超过100万对字符串的最长公共前缀。方法1:[hacking]暴力算法挂掉的场景是太多的字符串有较长的公共前缀，于是可以找出最长的一个串，计算出所有的串和这个最长串的最长公共前缀，然后在此基础上暴力。对于本题的数据，这个方法可以过。方法2:[suffix array]最长公共前缀是后缀数组的经典应用，但是这里有100万个查询，输入串的总长度可能达到600万，所以不确定是否能过。方法3:[trie]构造trie，然后有100万个lca查询，目测tarjan算法可以过。 |