题目链接

P3502 [POI 2010] CHO-Hamsters

解题思路 & 参考代码

考虑朴素 dp，$f_{i,j}$ 表示目前共匹配了 $i$ 个字符串，最后一个匹配的为第 $j$ 种字符串，显然转移的时候需要用到第 $x$ 种字符串的后缀和第 $y$ 种字符串的前缀可以匹配到的最大长度，容易 kmp 做到 $O(n^2 + \sum |S|)$ 的复杂度。

考虑到这个东西可以有 $\min,+$ 矩阵来加速，直接矩阵乘法优化 dp 即可，时间复杂度为 $O(n^3 \log m + \sum |S|)$，可以通过此题。

:::info[参考代码]

ll n,m;
string s[210];
ll len[210];
ll dis[210][210];
ll nxt[210][100010];
struct matrix{
    ll n,m,a[210][210];
    void _init(ll _n,ll _m)
    {
        n=_n,m=_m;
        forl(i,0,n+1)
            forl(j,0,m+1)
                a[i][j]=0;
    }
    friend matrix operator * (matrix x,matrix y)
    {
        matrix z;
        z._init(x.n,y.m);
        forl(i,0,x.n)
            forl(j,0,x.m)
            {
                z.a[i][j]=LM;
                forl(k,0,y.m)
                    Min(z.a[i][j],x.a[i][k]+y.a[k][j]);
            }
        return z;
    }
}Pw,ans;
void solve()
{
    cin>>n>>m;
    forl(i,1,n)
        cin>>s[i],
        len[i]=s[i].size(),
        s[i]=' '+s[i];
    dis[0][0]=LM;
    forl(i,1,n)
    {
        dis[0][i]=len[i],dis[i][0]=LM;
        ll R=0;
        forl(j,2,len[i])
        {
            while(R && s[i][j]!=s[i][R+1])
                R=nxt[i][R];
            if(s[i][j]==s[i][R+1])
                R++;
            nxt[i][j]=R;
        }
    }
    forl(i,1,n)
        forl(j,1,n)
        {
            if(i==j)
            {
                dis[i][j]=len[i]-nxt[i][len[i]];
                continue;
            }
            ll R=0;
            forl(k,1,len[i])
            {
                while(R && s[i][k]!=s[j][R+1])
                    R=nxt[j][R];
                if(s[i][k]==s[j][R+1])
                    R++;
                dis[i][j]=len[j]-R;
            }
        }
    Pw._init(n,n);
    forl(i,0,n)
        forl(j,0,n)
            Pw.a[i][j]=dis[i][j];
    ans=Pw;
    m--;
    while(m)
    {
        if(m&1)
            ans=ans*Pw;
        Pw=Pw*Pw;
        m>>=1;
    }
    ll minn=LM;
    forl(i,0,n)
        Min(minn,ans.a[0][i]);
    cout<<minn<<endl;
}

:::

讲一下自己的大致思路。

先说一下暴力分：

这是我看到此题的第一反应：dp，复杂度为$O(n^2m)$。

我们先定义两字符串间的距离值$dis[i][j]$，表示$j$号串拼接在$i$号串之后，需要在$i$号串末尾添加的字符数。

此时我们再用$dp[i][j]$ 表示这个串里应经有了$i$个字符串，并且最后出现在该串里的子串是$j$号串的答案，显然可以按下转移：

$dp[1][i]=len(i)$，表示取1个字符串，并且是第$i$个字符串结尾，那么它的代价显然是$len(i)$

$dp[i][j] = min\{ dp[i-1][k]+dis[k][j]\}$，我们在$k$号字符串 后面拼接上$j$号字符串，添加字符量即为$dis[k][j]$。

注意转移时的顺序，应该先枚举$i$，再枚举$j$和$k$。读者可以想想，为什么？

贴一下dp的核心部分：

void DP() {
  memset(dp, 0x7f, sizeof(dp));
  for (int i = 1; i <= n; i++)
    dp[1][i] = len[i];
  for (int i = 2; i <= m; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++)
        dp[i][j] = min(dp[i][j], dp[i - 1][k] + dis[k][j]);
}

所以，我们分析想到了转移公式，那么答案即为$min\{ dp[m][i]\}$，其中$1\le i\le n$（因为一共有$n$种字符串）。

看到有$n$个字符串，并且是一个个字符串首尾拼接而成的，我们很自然的想到AC自动机。

在本人经过长达1小时的思考后，终于想出了正解。。。

本人比较擅长KMP算法，看到这题，果断想到是KMP，粗略计算一下，KMP()函数部分的复杂度为$O(\sum^{n}_{i=1}\sum^{n}_{j=1}(len(i)+len(j)))= O(\sum^{n}_{i=1}(n\times len[i]+\sum |S|))≈ O(n|S|)$，稍微带一点小常数。

下面是KMP部分的代码：

void KMP() {
  // kmp1：单个字符串内匹配
  for (int p = 1; p <= n; p++) {
    int j = 0;
    for (int i = 2; i <= len[p]; i++) {
      while (j > 0 && str[p][j + 1] != str[p][i])
        j = nxt[p][j];
      if (str[p][j + 1] == str[p][i]) j++;
      nxt[p][i] = j;
    }
  }
  
  // kmp2：两两字符串间匹配
  for (int p1 = 1; p1 <= n; p1++) {
    for (int p2 = 1; p2 <= n; p2++) {
      int j = 0;
      for (int i = 2; i <= len[p1]; i++) {
        while (j > 0 && str[p2][j + 1] != str[p1][i])
          j = nxt[p2][j];
        if (str[p2][j + 1] == str[p1][i]) j++;
        if (i == len[p1]) {
          a.v[p1][p2] = len[p2] - j;
        }
      }
    }
  }
}

好，既然我们已经预处理KMP得到了两两字符串间的关系（末尾添加字符量），那么我们接下来考虑如何优化dp。

读者不妨再回头去看看dp的转移部分，有没有发现，这个转移方式似曾相识？

没错，这似乎与floyd的转移代码有异曲同工之妙。它的转移方式，跟floyd是一模一样的！那么这个转移方式等价于一个$O(n^3)$的floyd，我们从另一种角度去考虑如何优化这个伪的floyd。

在优化复杂度之前，请读者先考虑一些细节问题：

首先，将这个转换成floyd，是基于点操作的，我们可以将每一个字符串的每一个字符都视作是一个点，这下次就是彻彻底底的floyd了233。

其次，我们不知道该从第几号字符串作为整一个串的起点，所以我们考虑加一个超级源，设它为$0$号串，将$0$号串连接到第$i(1\le i\le n)$号串。从$0$到$i$的权值为$dis[0][i] = len(i)$，从$i$到$0$显然做不到，所以设置为无穷大，即：$dis[i][0] = inf$。

好了，接下来我们考虑如何去优化复杂度。

很显然，数据范围中$m$的范围特别大，已经到了$1e9$的地步，此时我们就数据范围倒推，显然不可能是$O(m)$线性扫，所以极大可能是$O(\sqrt{m})$或者$O(logm)$。

如果是$O(\sqrt{n})$，那么一定有关于开根号的东西，但floyd显然不可能与根号发生关系，所以暂时排除。

那么我们发现只可能是$O(logm)$的复杂度内运行floyd，此时我们果断想到：与$log$有关的，极大可能是快速幂，但这不是$a^p$的形式，而是一个二维的幂形式。

相信读者都已经猜到了，这就是矩阵快速幂！

综上，我们发现，这道题可以在$O(n|S|+n^2*log\space m)$的复杂度内跑出结果，常数较小，值得一试。

同时，作为前人，也提醒一下大家：这道题可能要开$-O2$才能$AC$,数据#1稍微有点卡常数！

献上代码，完美撒花：

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long long ll;

const int N = 202;
const int M = 100002;
string str[N];
int len[N], t;
int nxt[N][M];
//int dis[201][201];
int n, m;

struct MAT {
  ll v[N][N];
  void print() {
    for (int i = 0; i <= n; i++, puts(""))
      for (int j = 0; j <= n; j++)
        printf("%lld ", v[i][j]);
    putchar('\n');
  }
} ans, a;

MAT operator * (MAT a, MAT b) {
  MAT c;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      c.v[i][j] = 1e15;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++)
        c.v[i][k] = min(c.v[i][k], a.v[i][j] + b.v[j][k]);  
  return c;
}

void KMP() {
  // init
  a.v[0][0] = 1e15;
  for (int p = 1; p <= n; p++)
    a.v[0][p] = len[p], a.v[p][0] = 1e15;
  
  // kmp1
  for (int p = 1; p <= n; p++) {
    int j = 0;
    for (int i = 2; i <= len[p]; i++) {
      while (j > 0 && str[p][j + 1] != str[p][i])
        j = nxt[p][j];
      if (str[p][j + 1] == str[p][i]) j++;
      nxt[p][i] = j;
    }
  }
  
  // kmp2
  for (int p1 = 1; p1 <= n; p1++) {
    for (int p2 = 1; p2 <= n; p2++) {
      int j = 0;
      for (int i = 2; i <= len[p1]; i++) {
        while (j > 0 && str[p2][j + 1] != str[p1][i])
          j = nxt[p2][j];
        if (str[p2][j + 1] == str[p1][i]) j++;
        if (i == len[p1]) {
          a.v[p1][p2] = len[p2] - j;
        }
      }
    }
  }
  
  /*
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      printf("dis[%d][%d] = %d\n", i, j, dis[i][j]);
  */
}

void ksm() {
  //a.print();
  
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      ans.v[i][j] = a.v[i][j];
  
  // woc, m--!   
  m--;
  while (m > 0) { 
    //printf("in ksm %d\n", m);
    //ans.print(); a.print();
    //printf("----------\n");
    if (m & 1) ans = ans * a;
    a = a * a; m >>= 1;
  }
}

bool check() {
  for (int i = 1; i <= n; i++) {
    if (len[i] == 1) return 1;
  }
  return 0;
}

signed main() {
  scanf("%lld%lld", &n, &m);
  if (m == 0) {
    puts("0"); return 0;
  }
  
  for (int i = 1; i <= n; i++) {
    cin >> str[i];
    len[i] = str[i].size();
    str[i] = ' ' + str[i];
  }
  
  if (check()) {
    printf("%lld\n", m);
    return 0;
  }
  
  KMP();
  ksm();
  
  ll anss = 2e15;
  for (int i = 1; i <= n; i++)
    anss = min(anss, ans.v[0][i]);
  printf("%lld\n", anss);
  return 0;
}

附：如果有$WA$的网友，我在这里提供几组$hack$数据，您可以不妨一测。

$\color{red}hack1.in$

5 100
a
b
c
d
e

$\color{red}hack1.out$

100

$\color{red}hack2.in$

1 0
a

$\color{red}hack2.out$

0

$\color{red}hack3.in$

4 5
ab
bc
cd
de

$\color{red}hack3.out$

7