有\(n\)个字符串互不包含，\(\sum len\le 10^5\)。求一个最短的字母序列的长度，使得这个字母序列中出现了\(m\)次那\(n\)个字符串。举个例子：
n=3,m=4
ab
bc
ca
那么符合要求的字符串有
abcabc (ab,bc各出现两次，共4次)
abcab (ab出现两次，bc和ca各出现一次，共4次)
所以输出为5，即abcab为最短的符合要求的。\(n\le 200,m\le 10^9\)。
思路
读懂题就能知道，让一个字符串的后部分和前部分重合来减小需要的字符串长度。于是可以通过kmp（把一个字符串放在第一个，其他接在后面）得到每个字符串后面加上多少个字符可以加成另一个。
于是我自己就做不下去了，当时的想法是如何达到最小，直接在里面找一下之类的。其实这个\(n\)这么小，我们完全没有必要一开始就把它限制住，而是可以直接以矩阵为单位进行转移。这样就得出了一个做法。
我们要做的其实是把一个初始矩阵（A[i][i]=len(s[i]))转移\(m\)次的基础矩阵（kmp得到的每个加上多少个字符得到多一个）。其实，转移顺序是无关的，所以可以通过把基础矩阵自己转移（类似快速幂的方法）\(m\)次，用它来转移初始矩阵。最后在得到的矩阵中求最小值即可。
这题的关键在于以矩阵为单位转移，而不是从如何直接找出最小的那个来做。同样的做法可以解决走k步最短路问题，其实跟这个题本质上是相同的。
前面求出基础矩阵也可以用AC自动机来做，每个点记录下面有哪些字符串，从每个结束节点开始沿着fail跳。复杂度和kmp是一样的。
总的复杂度为\(O(n\sum len+n^3\log m)\)。
代码
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long giant;
const int maxn=201;
const int maxl=2e5;
const giant inf=1e15;
int n,m,nxt[maxl];
string s[maxn],t;
struct Mat {
giant a[maxn][maxn];
inline void clear() {memset(a,0,sizeof a);}
Mat () {clear();}
inline giant* const operator [] (const int x) {return a[x];}
inline void operator = (const Mat &b) {
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) a[i][j]=b.a[i][j];
}
inline void INF() {
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) a[i][j]=inf;
}
} a,b,bas;
void deal(int the) {
t=" "+s[the];
for (int i=1;i<=n;++i) if (i!=the) t+=" "+s[i];
int l=t.length()-1,j=nxt[1]=0;
for (int i=2;i<=l;++i) {
for (;j && t[j+1]!=t[i];j=nxt[j]);
nxt[i]=(t[j+1]==t[i]?++j:j);
}
int p=s[the].length(),tl=p;
bas[the][the]=tl-nxt[p];
for (int i=1;i<=n;++i) if (i!=the) {
p+=s[i].length()+1;
bas[i][the]=tl-nxt[p];
}
}
Mat update(Mat &a,Mat &b) {
static Mat ret;
ret.INF();
for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) if (a[i][k] && b[k][j]) ret[i][j]=min(ret[i][j],a[i][k]+b[k][j]);
return ret;
}
void up(int cs) {
for (;cs;cs>>=1,bas=update(bas,bas)) if (cs&1) b=update(b,bas);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=1;i<=n;++i) {
string &x=s[i];
cin>>x;
a[i][i]=(giant)x.length();
}
if (m==1) {
giant ans=inf;
for (int i=1;i<=n;++i) ans=min(ans,(giant)s[i].length());
cout<<ans<<endl;
return 0;
}
for (int i=1;i<=n;++i)
deal(i);
b=bas;
up(m-2);
a=update(a,b);
giant ans=inf;
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) ans=min(ans,a[i][j]);
cout<<ans<<endl;
return 0;
}
转载于:https://www.cnblogs.com/owenyu/p/7110154.html
