[ABC287E] Karuta 题解

pies_0x · 2024-08-24 18:56:31 · 题解

[ABC287E] Karuta 题解

按字典序将字符串排序后，对于，\mathrm{LCP}(S_i,S_j)，|i-j| 越小，\mathrm{LCP}(S_i,S_j) 越大。

为什么？我们设三个字符串按字典序依次为 a,b,c。

如果 a,b,c 的长度相等，则：

根据字典序的判断方法，\mathrm{LCP}(a,b) 不可能小于 \mathrm{LCP}(a,c)。

如果 a,b,c 的其中两个字符串长度不相等，我们可以假想一种字符来补全长度，这种字符与任何字符不同，包括自身，这就成了上一种情况。

对于 \mathrm{LCP} 的计算，我们可以通过二分 \mathrm{LCP}(a,b) 的方式来计算。

具体实现时，\mathrm{LCP}(a,b) 通过二分来计算。

Code

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define N 500005

int n;
struct bind{int id;string s;}binds[N];
int ans[N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>binds[i].s,
        binds[i].id=i;
    sort(binds+1,binds+n+1,[](bind a,bind b){return a.s<b.s;});
    for(int i=1;i<n;++i)
    {
        int l=0,r=min(binds[i].s.length(),binds[i+1].s.length());
        while(l<r-1)
        {
            int mid=l+r>>1;
            if(binds[i].s.substr(0,mid)==binds[i+1].s.substr(0,mid))
                l=mid;
            else r=mid-1;
        }
        int answer=binds[i].s.substr(0,r)==binds[i+1].s.substr(0,r)?r:l;
        ans[binds[i].id]=max(ans[binds[i].id],answer);
        ans[binds[i+1].id]=answer;
    }
    for(int i=1;i<=n;++i)
        printf("%d\n",ans[i]);
    return 0;
}