一道不错的题。
首先仔细审题,是覆盖而不是蓝书上的完全匹配,因而没有长度必须为原串长度因数的限制,于是$n-nxt[n]$一定能覆盖长为$n$的串。
考虑将宽度和高度分开:
宽度上,找出一个最小的pos,满足对于所有$1\le i \le n,[1,pos]$能覆盖串$i$
这个暴力即可,复杂度$O(nm^2)$
高度上,由于我们已经保证对于所有$1\le i \le n,[1,pos]$能覆盖串$i$,也就是每一行都已经合法了,找出最小的$h$,使串$[1,h]$能覆盖整个矩阵即可。
这个如何快速求?
将每一行看做一个字符,用kmp处理$next[]$,则$h=n-next[n]$(将kmp对于字符的比较转换为对字符串的比较即可)
输入输出量较大,我用字符数组代替了string.
//Wan Hong 2.2
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 10011
#define MAXM 111
char a[MAXN][MAXM];
bool p[MAXM];//p[i]=1:[1,i]能覆盖所有串,或者说pos=min{i|p[i]=1}
ll nxt[MAXN];
ll n,m;
bool check(ll x,ll k)//[1,k]能否覆盖串x
{
ll it=1;
for(ll i=k+1;i<=m;++i)
{
if(a[x][i]==a[x][it])
{
++it;
if(it>k)it=1;
}
else return 0;
}
return 1;
}
int main()
{
n=read(),m=read();
memset(p,1,sizeof p);
for(ll i=1;i<=n;++i)
{
scanf("%s",a[i]+1);
for(ll j=1;j<=m;++j)
if(p[j])p[j]&=check(i,j);//注意要对每个串都满足,所以我使用&=
}
ll min_w=0;//即pos
for(ll i=1;i<=m;++i)
if(p[i])
{
min_w=i;break;
}
ll j=0;
for(ll i=2;i<=n;++i)//kmp求解h
{
while(j&&strcmp(a[j+1]+1,a[i]+1))j=nxt[j];//从1开始用,那么比较时要+1
if(!strcmp(a[j+1]+1,a[i]+1))++j;
nxt[i]=j;
}
printf("%lld",min_w*(n-nxt[n]));
return 0;
}
%%%%%
$Orz$原来这题的$kmp$是用来求高度的匹配的,$wcsl$
Orz
whsstory强啊!
Orz
好像写的不是很清楚,我太菜了【快哭了】