自动搬运

查看原文

来自洛谷，原作者为

	Thunder_S 咖啡馆与广场有三个街区，就像霓虹灯到月亮的距离。

搬运于2025-08-24 22:08:45，当前版本为作者最后更新于2021-05-05 10:38:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能更好的阅读体验

题目大意：有$N$种长度为$L$的字符串和一个匹配串$s$，每种都有无数个，现选出$K$个字符串，从上到下排成一个$K\times L$的字符矩阵，从左上角开始，从上到下，从左到右顺序写下各个字符，得出一个长度为$K\times L$的字符串$S$，且$s$是$S$的子串，最小化$K$和一种排列方案。

考虑字符串哈希，将所有子串用27进制压缩存到哈希表中（即每个字符串的任意位置开头和任意位置结尾），同时记录每个串所在的字符串的编号和开头所在的位置。

从小到大枚举$K$，那么第一个合法$K$就是答案。找出当前$K$下匹配串$s$被分成的$K$个小串。

如：$s=\texttt{abcde},K=3$

3个小串分别是$\texttt{ad},\texttt{be},\texttt{c}$

将这$K$个小串以上述方法压缩，在哈希表中查找。

若第$i$个小串在第$u$个字符串中，开头在第$j$列，那么$bz(i,j)=u$，表示第$i$个小串的开头在第$j$列可以在第$u$个字符串中找到。

再枚举$s$的第一个子串的开头的行$i$，列$j$，在$bz$中查找，如果第$j$或者$j+1$列都有对应的$u$值，那么就是合法答案。

也就是说，在这种情况下，如果一些$bz(u,j)$和另一些$bz(u,j+1)$都有值（$u$表示$s$的第$u$个子串），那么就合法（$j$还是$j+1$看$i$）。

#include<cstdio>
#include<cstring>
#define md 2999999
#define hashmd 5100001 
using namespace std;
int n,l,m,id,now,num,mi[105],pos[505001][2],nxt[505001],head[5100001],hs[5100001],bj[205][205],c[205][205];
bool flag;
char s[105][105],ss[205];
void add(int x,int i,int j)
{
	pos[++num][0]=i;pos[num][1]=j;
	nxt[num]=head[x];
	head[x]=num;
}
void hash(int x,int i,int j)
{
	int p=x;
	while (hs[p])
	{
		if (hs[p]==x)
		{
			add(p,i,j);
			return;
		}
		p=(p+1)%hashmd;
	}
	hs[p]=x;
	add(p,i,j);
}
void find(int x,int r)
{
	int p=x;
	while (hs[p])
	{
		if (hs[p]==x)
		{
			for (int i=head[x];i;i=nxt[i])
				c[r][pos[i][1]]=pos[i][0],bj[r][pos[i][1]]=id;
			return;
		}
		p=(p+1)%hashmd;
	}
}
int main()
{
	mi[0]=1;
	for (int i=1;i<=100;++i)
		mi[i]=mi[i-1]*27%md;
	scanf("%d%d",&n,&l);
	for (int i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for (int j=1;j<=l;++j)
		{
			int x=1;
			for (int k=j;k<=l;++k)
			{
				x=(x+(s[i][k]-'a'+1)*mi[k-j+1]%md)%md;
				hash(x,i,j);
			}
		}
	}
	scanf("%s",ss+1);
	m=strlen(ss+1);
	for (int k=1;k<=m;++k)
	{
		++id;
		for (int j=1;j<=k;++j)
		{
			int x=1,ln=0;
			now=j;
			while (now<=m)
			{
				x=(x+(ss[now]-'a'+1)*mi[++ln]%md)%md;
				now+=k;	
			}
			find(x,j);	
		} 
		for (int i=1;i<=k;++i)
		{
			int h=k-i+1;
			for (int j=1;j<=l;++j)
			{
				flag=true;
				for (int u=1;u<=k;++u)
				{
					if ((u<=h&&bj[u][j]<id)||(u>h&&bj[u][j+1]<id))
					{
						flag=false;
						break;
					}
				}
				if (flag)
				{
					printf("%d\n",k);
					for (int u=h+1;u<=k;++u) printf("%d ",c[u][j+1]);
					for (int u=1;u<=h;++u) printf("%d ",c[u][j]);
					return 0;
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

感谢LZA的博客提供的帮助，ORZ：

https://blog.csdn.net/qq_39565901/article/details/87472261