【字典树】Atcoder Beginner Contest 287----E

题目：E - Karuta (atcoder.jp)

题解：这道题就是一个字典树求最长公共前缀的板子题。可以直接交板子。

但我在翻题解的时候发现了另一种思路，就是将字符串按字典序排列后，每一个字符串的LCA（最长公共前缀）一定是和相邻两个字符串的LCA中的一个。

板子做法：

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef unsigned long long ULL;
const ll mod = 1e9+7;
const int N = 5e5 + 5;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
int son[N][26],cnt[N],idx;

string s[N];
void insert(string s,int v)
{
    int p=0;
    for(int i=0;i<s.length();i++)
    {
        cnt[p]+=v;
        int u=s[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]+=v;
}
int query(string s)
{
    int p=0;
    int ans=0;
    for(int i=0;i<s.length();i++)
    {
        int u=s[i]-'a';
        if(!son[p][u]) return ans;
        p=son[p][u];
        if(cnt[p]==0) return ans;
        ans++;
    }
    return ans;
}
void slove()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        insert(s[i],1);
    }
    for(int i=1;i<=n;i++)
    {
        insert(s[i],-1);
        cout<<query(s[i])<<endl;
        insert(s[i],1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    slove();
    return 0;
}

第二种做法：

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef unsigned long long ULL;
const ll mod = 1e9+7;
const int N = 5e5 + 5;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
struct node{
    string s;
    int id;
    bool operator<(const node&t)const{
        return s<t.s; 
    }
}a[N];
int sum(int x,int y)
{
    int res=0;
    string s1=a[x].s,s2=a[y].s;
    int len=min(s1.size(),s2.size());
    for(int i=0;i<len;i++)
    {
        if(s1[i]!=s2[i]) break;
        res++;
    }
    return res;
}
void slove()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s;
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    int ans[N];
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++)
    {
        int maxn=0;
        if(i-1>0&&i-1<=n)
        {
            maxn=max(maxn,sum(i,i-1));
        }
        if(i+1>0&&i+1<=n)
        {
            maxn=max(maxn,sum(i,i+1));
        }
        ans[a[i].id]=maxn;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    slove();
    return 0;
}