Bzoj2085

, ,

Solution

令 $f[i][j]$ 表示包含了 $i$ 个字符串且最后一个时第 $j$ 个字符串时，所需要的最少字符数。

容易转移 $f[i][j]=\min f[i-1][k]+w(k,j)$

然后我们用矩阵乘法优化一下即可。

现在考虑求出 $w(k,j)$。因为 $n$ 比较小，考虑直接枚举 $i,j$。

然后用 $kmp$ 或者哈希直接枚举求就好了。

$O(\sum\sum \min(len_i,len_j)\le O(\sum\sum len_i+len_j)=O(n\sum len_i)$

左边第一个是 哈希 的复杂度，第二个是 kmp 的复杂度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 205
#define maxm 100005
#define debug() return puts("1"),0
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int 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();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int pw[maxm],ipw[maxm];
vector<int>suf[maxn],pre[maxn];
const int base=131,mod=1e9+7,MAXLEN=1e5,inf=1e18;
int n,m,len[maxn],Ans=inf;
string s[maxn];
struct Mat {
	int a[maxn][maxn];
	Mat (void) {memset(a,0x3f,sizeof(a));}	
	inline void clear(void) {for (int i=1;i<=n;i++) a[i][i]=0;}
	Mat operator *(const Mat &x) const {
		int i,j,k;Mat ans;
		for (i=1;i<=n;i++) {
			for (j=1;j<=n;j++)
			 	for (k=1;k<=n;k++)
			 	 	ans.a[i][j]=min(ans.a[i][j],a[i][k]+x.a[k][j]);
		}
		return ans;
	}
}tmp;
inline int power(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=ans*x%mod;
		y>>=1;x=x*x%mod;
	}
	return ans;
}
inline int W(int i,int l,int r) {return (suf[i][r]-suf[i][l-1]+mod)*ipw[l]%mod;}
signed main(void){
//  freopen("1.in","r",stdin);
	int i,j,k;
	read(n);read(m);
	for (pw[0]=1,i=1;i<=MAXLEN;i++) pw[i]=pw[i-1]*base%mod;
	for (ipw[MAXLEN]=power(pw[MAXLEN],mod-2),i=MAXLEN;i>=1;i--) ipw[i-1]=ipw[i]*base%mod;
	for (i=1;i<=n;i++) {
		cin>>s[i];len[i]=s[i].size();s[i]='_'+s[i];
		suf[i].resize(len[i]+5);pre[i].resize(len[i]+5);
		for (j=1;j<=len[i];j++) suf[i][j]=(suf[i][j-1]+pw[j]*(s[i][j]-'a'+1))%mod;
	}
	for (i=1;i<=n;i++) 
		for (j=1;j<=n;j++) {
			tmp.a[i][j]=len[j];
			for (k=min(len[j],len[i])-1;k>=1;k--) 
				if (W(i,len[i]-k+1,len[i])==W(j,1,k)) {tmp.a[i][j]-=k;break;}
		}
	m--;Mat ans;ans.clear();
	while (m) {
		if (m&1) ans=ans*tmp;
		tmp=tmp*tmp;m>>=1;
	}
	for (i=1;i<=n;i++) {
		for (j=1;j<=n;j++)
		 	Ans=min(Ans,ans.a[i][j]+len[i]);
	}
	printf("%lld",Ans);
	return 0;
}