1 条题解

  • 1
    @ 2022-7-21 21:35:13
    #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;
    }
    
    • 1

    信息

    ID
    4181
    时间
    1000ms
    内存
    63MiB
    难度
    10
    标签
    递交数
    2
    已通过
    0
    上传者