霉球研究

C++(clang++ 11.0.1) 解法, 执行用时: 1422ms, 内存消耗: 46804K, 提交时间: 2023-02-13 00:15:35

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> void min(T &x,T y){y<x?x=y:T();}
const int N=1e5+10,lim=200,base=97;
int n,m,cnt,val[N],f[510][N],dp[2][N];
char s[N],t[N];
namespace SAM
{
    int lst,tot;
    int ch[N<<2][26],fa[N<<2],len[N<<2];
    inline void clear()
    {
        for(int i=0;i<=tot;i++)
			memset(ch[i],0,sizeof(ch[i])),fa[i]=len[i]=0;
        lst=tot=1;
        return;
    }
    inline void insert(int c)
    {
        int p=lst,np=++tot;len[np]=len[p]+1;lst=np;
        for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if(!p)
        {
        	fa[np]=1;
        	return;
		}
        int q=ch[p][c];
        if(len[q]==len[p]+1)
		{
			fa[np]=q;
			return;
		}
        int nq=++tot;
        fa[nq]=fa[q],len[nq]=len[p]+1;
        memcpy(ch[nq],ch[q],sizeof(ch[q]));
        for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        fa[np]=fa[q]=nq;
        return;
    }
}
unordered_map<ull,int>hs;
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		hs.clear();cnt=0;
		scanf("%s%d",s+1,&m);n=strlen(s+1);
		int minlen=1e9;
		for(int i=1;i<=m;i++)
		{
			scanf("%s",t+1);int len=strlen(t+1);
			min(minlen,len);
			if(len<=lim)
			{
				for(int j=1;j<=len;j++)
				{
					ull sum=0;
					for(int k=j;k<=len;k++)
					{
						sum=sum*base+t[k]-'a'+1;
						if(hs.count(sum)) min(hs[sum],len);
						else hs[sum]=len;
					}
				}
			}
			else
			{
				SAM::clear();val[++cnt]=len;
				for(int j=len;j>=1;j--) SAM::insert(t[j]-'a');
				for(int j=n,p=1,len1=0;j>=1;j--)
				{
					int c=s[j]-'a';
					for(;p&&!SAM::ch[p][c];p=SAM::fa[p]);
					min(len1,SAM::len[p]);
					p=SAM::ch[p][c];len1++;
					if(!p) p=1;
					min(len1,SAM::len[p]);
					f[cnt][j]=len1;
				}
			}
		}
		for(int i=0;i<=n;i++) dp[0][i]=dp[1][i]=1e9;
		dp[0][0]=0;
		for(int i=0;i<=n-1;i++)
		{
			for(int typ=0;typ<=1;typ++)
			{
				min(dp[typ][i+1],dp[typ][i]+1);
				
				ull sum=0;
				for(int j=i+1;j<=i+lim&&j<=n;j++)
				{
					sum=sum*base+s[j]-'a'+1;
					if(hs.count(sum)) min(dp[1][j],dp[typ][i]+hs[sum]-(j-i));
                    else break;
				}
				
				for(int j=1;j<=cnt;j++)
					min(dp[1][i+f[j][i+1]],dp[typ][i]+val[j]-f[j][i+1]);
			}
		}
		min(dp[1][n],n+minlen);
		printf("%d\n",dp[1][n]);
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 1407ms, 内存消耗: 198164K, 提交时间: 2022-10-30 12:28:47

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

const int N = 4e5 + 5;
int tot, lst, fa[N], len[N];
array<int, 26> ch[N];

void ins(int c) {
    int p = lst, np = lst = ++tot;
    len[np] = len[p] + 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) { fa[np] = 1; return; }
    int q = ch[p][c];
    if (len[q] == len[p] + 1) {
        fa[np] = q;
    } else {
        int nq = ++tot;
        len[nq] = len[p] + 1, ch[nq] = ch[q];
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
}

void solve() {
    for (int i = 1; i <= tot; i++) {
        fa[i] = len[i] = 0;
        ch[i].fill(0);
    }
    tot = lst = 1;
    string s;
    cin >> s;
    int m = s.size();
    vector<int> pos(m);
    for (int i = m - 1; ~i; i--) {
        ins(s[i] - 'a');
        pos[i] = lst;
    }
    int n;
    cin >> n;
    vector<string> t(n);
    for (auto &x : t) {
        cin >> x;
        reverse(x.begin(), x.end());
        lst = 1;
        for (char c : x) {
            ins(c - 'a');
        }
    }
    sort(t.begin(), t.end(), [&](const auto &p, const auto &q) {
        return p.size() < q.size();
    });
    vector<vector<int>> G(tot + 1);
    for (int i = 2; i <= tot; i++) {
        G[fa[i]].push_back(i);
    }
    vector<int> ord;
    auto dfs = [&](auto self, int u) -> void {
        ord.push_back(u);
        for (int v : G[u]) {
            self(self, v);
        }
    };
    dfs(dfs, 1);
    vector<pair<int, vector<int>>> tr;
    for (int i = 0, j; i < n; i = j) {
        vector<int> best(tot + 1);
        for (j = i; j < n && t[i].size() == t[j].size(); j++) {
            int cur = 1;
            for (char c : t[j]) {
                cur = ch[cur][c - 'a'];
                for (int i = cur; i && !best[i]; i = fa[i]) {
                    best[i] = i;
                }
            }
        }
        for (int u : ord) {
            for (int v : G[u]) {
                if (!best[v]) best[v] = best[u];
            }
        }
        tr.emplace_back(t[i].size(), best);
    }
    vector<int> f(m + 1, 1e9);
    for (int i = 0; i < m; i++) {
        for (auto &[l, best] : tr) {
            int t = min(m - i, len[best[pos[i]]]);
            f[i + t] = min(f[i + t], min(i, f[i]) + l - t);
        }
        f[i + 1] = min(f[i + 1], f[i] + 1);
    }
    cout << f[m] << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

详情