[JZOJ3159] [P5254]「JSOI2013」『字符串哈希』『枚举』广告计划

题解 字符串哈希 枚举
可能更好的阅读体验

题目

如今，在建筑的墙面上或者篱笆桩的表面上涂上一些广告，是一种新的吸引眼球的方法。

现在，小G 运营的一家小公司，决定也试着这样做做广告。小G 在他的篱笆桩上腾出了一些地方供广告使用。每一个篱笆桩都是一个水平的1*1*L 的4 棱柱，其中有一个1*L 的面是可以做广告的。1*L 的面上划出了L 个1*1 的小正方形（更具体地说是连续L 个水平排列的正方形），每个正方形内写上一个字母。

​ 时间久了，广告做多了难免会出现一些比较麻烦的情况，比如计划改变或者制作出错，因此小G 的仓库里面积累了好多没有用的，上面已经写上L 个字母的篱笆桩。（所有的篱笆桩的大小都是一样的，他们唯一的区别仅仅在于上面写了什么字母）。

​ 小G 决定对于这些篱笆桩进行重新利用，并且有了一些新的想法。

​ 如果将这些篱笆桩竖直的叠放起来，并且依次从左往右，对于每一个篱笆桩顺次从上到下读出上面的字母，那么我们可以得到一些新的比较长的单词，如下图：

​ 这些新的单词能满足小G 的一些新的需要。当然，基于美学考虑，小G 是不允许你删改篱笆桩上已经写上的字母的。

​ 我们更具体地描述这个过程。我们将K 个长度为L 的篱笆桩叠在一起，可以得到一个写有K行L 列共K*L 个字母的面，每一个字母都在对应的唯一的格子里。我们从左上角开始依次向下读出每一个字母可以得到一个字母的序列，比如上图中的这个例子，那么我们读出的结果就是“TOEIIZENITKN”。如果，这个串中有我们所需要的单词，那么显然我们只需要将一些格子刷白，就可以得到我们所需要的了。举个例子，比如小G 想要给圣彼得堡的足球队泽尼特队做个广告，那么很显然只要按照上图中的做法就可以达到小G 想要的效果了。

​ 现在小G已经想好了要做怎样的广告，同时也提供给你了小G仓库中的篱笆桩的类型的描述，你可以认为每一种类型的篱笆桩都是有无数个的。现在小G 想知道至少需要多少个篱笆桩叠起来才可以做出小G 想要的广告。

$1\le N,L\le 100$,$1\le |s|\le200$

题解

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

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

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

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

3个小串分别是$\text{ad},\text{be},\text{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$）

Code

#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