[ABC287E] Karuta 题解

FFTotoro · 2023-01-31 20:59:21 · 题解

本题需要使用字典树。

先将所有的字符串存进字典树，用 t_{p,x} 表示连在编号为 p 的结点下方的字符 x（这里的 x 并不是指小写字母 \texttt{x}，而是一个字符型变量）。每次插入只用不断往下“翻”就可以了。

然后对于每个字符串，忽略字典树里它“独有的”结点，然后看看最深可以匹配到多深——这个深度即为这个字符串的答案。

放代码：

#include<bits/stdc++.h>
using namespace std;
int t[500001][26],w,r[500001];
void insert(string s){
  int p=0;
  for(char i:s){
    int x=i-97;
    if(!t[p][x])t[p][x]=++w;
    else r[t[p][x]]++; // 统计经过每个结点的字符串是否大于一个，如果多于一个那么 r[t[p][x]] 应该是大于 0 的
    p=t[p][x]; // 前往下一个结点，“往下翻”
  }
}
int find(string s){
  int p=0,c=0;
  for(char i:s){
    int x=i-97;
    if(r[t[p][x]])c++; // 如果不止一个，就继续搜下去
    else break; // 否则退出
    p=t[p][x];
  }
  return c;
}
main(){
  ios::sync_with_stdio(false);
  int n,m=0; cin>>n;
  vector<string> a(n);
  for(auto &i:a)cin>>i,insert(i);
  for(auto i:a)cout<<find(i)<<endl;
  return 0;
}