Since the question involves suffixes, it is not difficult to think of using a trie tree to deal with it.
By flipping each string and inserting it into the trie, the suffix becomes a prefix, making it easier to process.
condition
LCS
(
A
,
B
)
≥
max
?
(
∣
A
∣
,
∣
B
∣
)
?
1
\text{LCS}(A,B) \ge \max(|A|,|B|)-1
LCS(A,B)≥max(∣A∣,∣B∣)?1, explanation
∣
∣
A
∣
?
∣
B
∣
∣
≤
1
\left||A|-|B|\right|\le1
∣∣A∣?∣B∣∣≤1.
So two strings rhyme if and only if they are father-son or brother in the trie tree.
Considering tree DP, let
f
i
f_i
fi? means
i
i
The length of the longest sequence on the rightmost side of the sequence represented by i,
v
a
l
i
val_i
vali? represents the node
i
i
i whether (1/0) has a word,
s
z
i
=
∑
x
∈
s
o
n
i
v
a
l
x
sz_i=\sum\limits_{x\in son_i}val_x
szi?=x∈soni?∑?valx?.
There is obviously a transfer
f
i
=
max
?
x
∈
s
o
n
x
(
f
x
)
+
s
z
i
?
1
+
v
a
l
i
f_i=\max\limits_{x\in son_x}(f_x) + sz_i-1 + val_i
fi?=x∈sonx?max?(fx?) + szi1 + vali?.
if
v
a
l
i
=
0
val_i=0
vali?=0, indicating that there is no string.
f
i
=
0
f_i=0
fi?=0.
When updating the answer, record the son
f
s
o
n
i
f_{son_i}
fsoni’s eldest and second eldest, plus the remaining sons and his own
v
a
l
val
val. (Perceptual understanding, only two positions in a chain are “free”, thus assuming the DP state)
This question is stuck in space, so when building the trie tree, it needs to be opened dynamically.
See the code for specific implementation.
#include<bits/stdc + + .h>
using namespace std;
const int N=3e6 + 10;
int cnt=1,n,f[N],ans;
char a[N];
struct node
{<!-- -->
vector<pair<int,int> > son;
int fa,val;
}tr[N];
void insert(int rt,char a[],int len)
{<!-- -->
for(int i=0;i<len;i + + ){<!-- -->
int x=a[i]-97;
for(auto j:tr[rt].son){<!-- -->
if(j.first==x){<!-- -->
rt=j.second;
goto a;
}
}
tr[rt].son.push_back(make_pair(x, + + cnt));
rt=tr[rt].son.back().second;
a:;
}
tr[rt].val + + ;
}
void dfs(int rt)
{<!-- -->
int aa=0,bb=0,x=0,y=0,sum=0;
for(auto i:tr[rt].son){<!-- -->
dfs(i.second);
sum + =tr[i.second].val;
f[rt]=max(f[rt],f[i.second]);
if(f[i.second]>aa){<!-- -->
bb=aa;
aa=f[i.second];
y=x;
x=tr[i.second].val;
}
else if(f[i.second]>bb) bb=f[i.second],y=tr[i.second].val;
}
f[rt] + =sum-x;
if(!tr[rt].son.size()) ans=max(ans,tr[rt].val);
else ans=max(ans,aa + bb-x-y + sum + tr[rt].val);
if(!tr[rt].val) f[rt]=0;
else f[rt] + + ;
}
int main()
{<!-- -->
scanf("%d", & amp;n);
for(int i=1;i<=n;i + + ){<!-- -->
scanf("%s",a);
int len=strlen(a);
reverse(a,a + len);
insert(1,a,len);
}
dfs(1);
cout<<ans;
}