| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1335212 | Faisal_Saqib | Rima (COCI17_rima) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <map>
// #include <bits/stdc++.h>
#include <vector>
using namespace std;
const long long mod=1e9+7,N=20;
int ans=0;
string s[N];
int dp[N];
// const int M=3e6+100;
// map<int,int> z[M],o[M];
int lcs(int i,int j)
{
int n=s[i].size(),m=s[j].size();
for(int p=0;p<min(n,m);p++)
{
if(s[i][p]!=s[j][p])
{
return p;
}
}
return min(n,m);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
reverse(begin(s[i]),end(s[i]));
}
sort(s,s+n);
reverse(s,s+n);
for(int i=0;i<n;i++)
{
// string s;
dp[i]=1;
for(int j=i-1;j>=0;j--)
{
if(lcs(i,j)+1>=max(s[i].size(),s[j].size()))
{
dp[i]=max(dp[i],dp[j]+1);
}
}
ans=max(ans,dp[i]);
// int l=s.size();
// int ohsh=0,zhsh=0;
// for(int j=l-1;j>=0;j--)
// {
// zhsh=(1ll*zhsh*29+(s[j]-'a'+1))%mod;
// if(j==1)ohsh=zhsh;
// }
// int dp=max({z[l-1][ohsh],z[l][zhsh],o[l][ohsh],o[l+1][zhsh]})+1;
// z[l][zhsh]=max(z[l][zhsh],dp);
// o[l][ohsh]=max(o[l][ohsh],dp);
// ans=max(ans,dp);
}
cout<<ans<<endl;
}