C++14(g++5.4) 解法, 执行用时: 22ms, 内存消耗: 13892K, 提交时间: 2018-08-17 15:28:57

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+10;
const int MOD=1e9+7;
const int INF=1e9+7;
typedef long long ll;
int ans[MAX],f[MAX];
int pre[MAX][30];
void getfail(char *s,int n)
{
    f[0]=f[1]=0;
    for(int i=1;i<n;i++)
    {
        int j=f[i];
        while(j&&s[i]!=s[j])j=f[j];
        f[i+1]=(s[i]==s[j]?j+1:0);
    }
    for(int i=0;i<=n;i++)
    for(int j=0;j<26;j++)
    {
        pre[i][j]=(i==0?0:pre[f[i]][j]);
        if(i<n)pre[i][s[i]-'a']=i+1;
    }
}
int tp[MAX];
void kmp(char *s,char *p,int m,int n)
{
    ans[0]=min(ans[0],m);
    getfail(s,m);
    int cur=0;
    tp[0]=0;
    for(int i=0;i<n;i++)
    {
        if(p[i]=='-')cur=max(cur-1,0);
        else tp[cur]=pre[tp[cur++]][p[i]-'a'];
        ans[i+1]=min(ans[i+1],m-tp[cur]);
    }
}
char s[5][MAX],p[MAX];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%s",s[i]);
    scanf("%s",p);
    int m=strlen(p);
    for(int i=0;i<=m;i++)ans[i]=INF;
    for(int i=1;i<=n;i++)kmp(s[i],p,strlen(s[i]),m);
    for(int i=0;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 19ms, 内存消耗: 2096K, 提交时间: 2022-08-09 16:24:23

#include<bits/stdc++.h>
using namespace std;
const int N=2000009;
void KMP(char *x,int *fail)
{
	int len=strlen(x);
	int i=0,j=-1;
	fail[0]=-1;
	while(i<len)
	{
		while(j!=-1&&x[i]!=x[j]) j=fail[j];
		fail[++i]=++j;
		if(x[i]==x[j])
		fail[i]=fail[j]; 
	 } 
}
char x[5][N],a[N];
int fail[N];
int ans[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	scanf("%s",x[i]);
	scanf("%s",a);
	int len=strlen(a);
	for(int i=0;i<=len;i++)
	ans[i]=1e9;
	int mi=1e9;
	for(int i=1;i<=n;i++)
	{
		int lens=strlen(x[i]);
		mi=min(mi,lens);
		KMP(x[i],fail);
		stack<int>q;
		int now=0;
		for(int j=0;j<len;j++)
		{
			if(a[j]=='-')
			{
				if(!q.empty()) q.pop();
				if(!q.empty()) now=q.top();
				else now=0;
			}
			else
			{
				while(x[i][now]!=a[j]&&now!=-1)
				now=fail[now];
				q.push(++now);
			}
			ans[j]=min(ans[j],lens-now);
		}
	}
	printf("%d\n",mi);
	for(int i=0;i<len;i++)
	printf("%d\n",ans[i]);
}