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

· · 题解

可能更好的阅读体验

题目大意：有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