140、依依的瓶中信.docx

解题思路

根据题目的描述，我们的目标是找出每条信息Si?与其它信息中，最长可以连续匹配的字符数量。我们需要找出与每条信息最相似的信息，这可以通过比较最长公共前缀来实现。由于所有的信息都是由小写英文字母组成，我们可以采用字典树(Trie)数据结构来存储这些信息，并便捷地查询最长公共前缀。

字典树是一种用于快速查询、插入和删除字符串的数据结构。每个节点代表一个字符串，每个节点的子节点代表在当前字符串后面添加一个字符后得到的新字符串。在这个问题中，我们可以利用字典树来存储所有的信息，并在每个节点处存储经过该节点的信息数量。

以下是详细的解题步骤：

初始化字典树：?创建字典树的节点数组?son[N][26]，其中?N?是信息的最大数量，26是小写英文字母的数量。son[i][j]?代表信息?i?在添加字符?j?后转移到的新信息。此外，我们还需要一个数组?cnt[N]?来存储经过每个节点的信息数量。

插入信息：?对于每条信息?Si，我们从根节点开始，按照信息中的字符顺序插入字典树。每经过一个节点，就将该节点的计数器加上当前信息的数量。

查询最长公共前缀：?对于每条信息?Si，我们需要找出与其最相似的信息，即最长可以连续匹配的字符数量。这可以通过从根节点开始，按照信息中的字符顺序在字典树中查找实现。每当我们找到一个字符，就检查当前节点的计数器。如果计数器为零，说明没有其它的信息与当前信息在这个位置具有相同的字符，因此我们可以返回当前已匹配的字符数量。否则，我们继续向下查找，直到信息的所有字符都被处理完。

处理所有的信息：?先插入所有的信息到字典树中，然后对于每条信息，先从字典树中删除，然后查询最长公共前缀，最后再重新插入到字典树中。这样可以确保查询最长公共前缀时不会比较信息与其自身。

以上的解题思路满足题目的限制条件，因为对于每条信息，插入和查询最长公共前缀的时间复杂度都是?O(∣Si∣)，其中∣Si∣?是信息的长度。因此，处理所有的信息的总时间复杂度是O(∑i=1N∣Si∣)，满足∑i=1N∣Si∣≤105?的限制。此外，字典树的空间复杂度是?O(N?26)，也满足N≤104?的限制。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

constintN=1e5+10;

intson[N][26],cnt[N],idx;

voidinsert(stringstr,intv)

{

intp=0;

for(inti=0;istr.size();i++){

cnt[p]+=v;

intu=str[i]-a;

if(!son[p][u])son[p][u]=++idx;

p=son[p][u];

}

cnt[p]+=v;

}

intquery(stringstr)

{

intp=0,ans=0;

for(inti=0;istr.size();i++){

intu=str[i]-a;

if(!son[p][u])returnans;

p=son[p][u];

if(cnt[p]==0)returnans;

++ans;

}

returnans;

}

strings[N];

intmain(){

intn;

cinn;

for(inti=1;i=n;i++){

cins[i];

insert(s[i],1);

}

for(inti=1;i=n;i++){

insert(s[i],-1);

coutquery(s[i])\n;

insert(s[i],1);

}

return0;

}

Java

importjava.util.*;

importjava.io.*;

publicclassMain{

staticfinalintN=(int)1e5+10;

staticint[][]son=newint[N][26];

staticint[]cnt=newint[N];

staticintidx=0;

static