[CERC2018]The ABCD Murderer

The first input line contains an integer $L (1 ≤ L ≤ 3 · 10^5)$ , the number of words found in the
newspapers. The next line contains the text of the ransom note. The text is not empty and
consists of lowercase English letters only. It is at most $3 · 10^5$ characters long.
Each of the next $L$ lines contains one word appearing in the newspapers, in lowercase English
letters. None of these words is empty or longer than the text of the ransom note. All words
appearing in the newspapers are listed in the input at least once. Sum of lengths of all words is
not greater than $3 · 10^5$
.

Output the minimal number of words Oscar has to cut out from the newspapers to compose his ransom note. If it is not possible to compose the ransom note, print −1. Each word has to be counted as many times as it is physically cut out from a newspaper.

C++ 解法, 执行用时: 131ms, 内存消耗: 57344K, 提交时间: 2022-03-01 17:21:04

#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
const int T = 300010;
const int S = 300010;
char s[S],ss[S];
queue<int> q;
int dp[300010][20];
int n, tr[T][26], fail[T], tot, len[N], siz[T];
int ask(int l,int r)
{
	if(l>r) return 1e9+7;
	int k=log2(r-l+1);
	return min(dp[l+(1<<k)-1][k],dp[r][k]);//反向 
 } 
int main()
{
    int i,j,u;
    scanf("%d",&n);
    scanf("%s",ss+1);
    for (i=1;i<=n;i++)
    {
        scanf("%s",s);
        int l=strlen(s);
        for(u=0,j=0;s[j];++j)
        {
            int c = s[j] - 'a';
            if (!tr[u][c]) tr[u][c] = ++tot;
            u = tr[u][c];
        }
        len[u]=l;
    }
    for(int i=0;i<26;i++)if(tr[0][i]){fail[tr[0][i]]=0;q.push(tr[0][i]);}
    while (!q.empty())
    {
        int u = q.front();q.pop();
        len[u]=max(len[u],len[fail[u]]);
        //有些点不是结尾点 通过跳fail转移len 
        for (int i=0;i<26;i++)
        {
            if (tr[u][i])
            {
                fail[tr[u][i]] = tr[fail[u]][i];
                q.push(tr[u][i]);
            }
            else tr[u][i] = tr[fail[u]][i];
        }
    }
    memset(dp,0x3f3f3f3f,sizeof(dp));dp[0][0]=0;
    int l=strlen(ss+1);u=0;
    for(int i=1;i<=l;i++)
    {
       u=tr[u][ss[i]-'a'];
	   dp[i][0]=ask(i-len[u],i-1)+1;
	   for(int j=1;j<20;j++)
	   {
	   	 if(i-(1<<j)+1<0) break;
	   	 dp[i][j]=min(dp[i][j-1],dp[i-(1<<j-1)][j-1]);
		} 
	}
	printf("%d",dp[l][0]>1e9?-1:dp[l][0]);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 130ms, 内存消耗: 57344K, 提交时间: 2023-05-07 11:00:12

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+11;
int n;
char s[N],ss[N];
int tr[N][26],len2[N],ne[N],cnt,dp[N][20];
queue<int>q;
void add(){
	int len=strlen(s),p=0;
	for(int j=0;j<len;j++){
		int v=s[j]-'a';
		if(!tr[p][v])tr[p][v]=++cnt;
		p=tr[p][v];
	}
	len2[p]=max(len2[p],len);
}
void kmp(){
	for(int i=0;i<26;i++){
		if(tr[0][i])q.push(tr[0][i]);
	}
	while(!q.empty()){
		int p=q.front();
		q.pop();
		len2[p]=max(len2[p],len2[ne[p]]);
		for(int i=0;i<26;i++){
			int j=tr[p][i];
			if(j){
				ne[j]=tr[ne[p]][i];
				q.push(j);
			}
			else tr[p][i]=tr[ne[p]][i];
		}
	}
}
int fx(int l,int r){
	if(l>r)return 1e9+7;
	int k=log2(r-l+1);
	return min(dp[r][k],dp[l+(1<<k)-1][k]);
}
int main(){
	scanf("%d%s",&n,ss+1);
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		add();
	}
	kmp();
	int le=strlen(ss+1),p=1;
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=le;i++){
		int v=ss[i]-'a';
		p=tr[p][v];
		dp[i][0]=fx(i-len2[p],i-1)+1;
		for(int j=1;j<20;j++){
			if(i-(1<<j)+1<0)break;
			dp[i][j]=min(dp[i][j-1],dp[i-(1<<j-1)][j-1]);
		}
	}
	if(dp[le][0]>1e9)cout<<-1;
	else cout<<dp[le][0];
}

详情