[ABC343G] Compress Strings

题目链接：https://www.luogu.com.cn/problem/AT_abc343_g

solution：
1.首先我们将给出的字符串中互相包含的消去，可以使用kmp求前后缀来完成。和这道题的写法一样https://www.luogu.com.cn/problem/CF1200E
2.我们发现给出的字符串最多只有20个，考虑状压来求解所有可能
3.我们注意到这道题只需要求出最小的长度即可，那么转移的代价就是后面拼接上去的字符串的有效长度。何为有效长度：因为两个字符串相接，有可能在前一个串的后缀和后一个串的前缀会出现重叠，有效长度就是后一个串的长度减去重复的这部分得到的长度。
4.开始转移 我们设dp[state][j] state为当前的选中的字符串（目前得到的母串）构成的集合，j是当前的母串以第 j 个字符串结尾 ，如此得到的母串长度。
5.转移，具体操作见代码。

vector<int> kmp(string s)
{
    int n=s.size();
    vector<int> nxt(n+1);
    for(int i=1,j=0;i<n;i++)
    {
        while(j&&s[i]!=s[j])
        {
            j=nxt[j];
        }
        j+=(s[i]==s[j]);
        nxt[i+1]=j;
    }
    return nxt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<string> S(n);
    for(int i=0;i<n;i++)
    {
        cin>>S[i];
    }
    vector<string> tmp;
    sort(all(S),[&](string a,string b){
        return a.size()<b.size();
    });
    for(int i=0;i<n;i++)
    {
        int flag=1;
        for(int j=i+1;j<n;j++)
        {
            vector<int> f=kmp(S[i]+'#'+S[j]);
            if(find(all(f),S[i].size())!=f.end())
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            tmp.push_back(S[i]);
        }
    }
    n=tmp.size();
    S=tmp;
    vector cost(n,vector<int> (n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j) continue;
            vector<int> f=kmp(S[j]+'#'+S[i]);
            cost[i][j]=S[j].size()-f.back();
        }
    }
    vector dp((1<<n),vector<int> (n,1e9));
    vector<string> res(1<<n);
    for(int i=0;i<n;i++)
    {
        dp[1<<i][i]=S[i].size();
    }
    for(int s=1;s<(1<<n);s++)
    {
        for(int i=0;i<n;i++)
        {
            if(s>>i&1)
            {
                for(int j=0;j<n;j++)
                {
                    if(!(s>>j&1))
                    {
                        dp[s|1<<j][j]=min(dp[s|1<<j][j],dp[s][i]+cost[i][j]);
                    }
                }
            }
        }
    }
    int ans=*min_element(dp.back().begin(),dp.back().end());
    cout<<ans<<'\n';
}