1 条题解
-
1
#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
- 上传者