题意:给一个n*k的循环字符串可能从任意地方断开,然后m个长度k的字符串,问你能不能用下面的字符串(每个最多用一次)构成上面的字符串,能循环移位
题解:对下面的串建ac自动机,记录字符串最后一个位置,然后把上面的串扩展k个,再在ac自动机上跑确定每个节点能匹配的字符串是谁,然后枚举k个位置作为起点,开始匹配,n个位置能匹配而且不重复即是答案
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-7;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=2000000+10,maxn=100000+10,inf=0x3f3f3f3f;
char s[N],p[N];
int a[N];
struct ACM{
int root,tot;
int Next[N][26],fail[N],End[N];
int newnode()
{
memset(Next[tot],-1,sizeof Next[tot]);
End[tot]=0;
return tot++;
}
void init(){tot=0;root=newnode();}
void ins(int id)
{
int now=root,n=strlen(s);
for(int i=0;i<n;i++)
{
if(Next[now][s[i]-'a']==-1)Next[now][s[i]-'a']=newnode();
now=Next[now][s[i]-'a'];
}
End[now]=id;
}
void build()
{
queue<int>q;
fail[root]=root;
for(int i=0;i<26;i++)
{
if(Next[root][i]==-1)Next[root][i]=root;
else
{
fail[Next[root][i]]=root;
q.push(Next[root][i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(Next[now][i]==-1)Next[now][i]=Next[fail[now]][i];
else
{
fail[Next[now][i]]=Next[fail[now]][i];
q.push(Next[now][i]);
}
}
}
}
void query(int n,int k)
{
// for(int i=1;i<=tot;i++)
// {
// printf("%d %d --",i,End[i]);
// for(int j=0;j<4;j++)printf("%d ",Next[i][j]);
// puts("");
// }
int now=root;
for(int i=0;p[i];i++)
{
now=Next[now][p[i]-'a'];
a[i]=End[now];
}
for(int i=0;i<k;i++)
{
now=Next[now][p[i]-'a'];
a[n*k+i]=End[now];
}
for(int i=0;i<k;i++)
{
bool ok=1;vi v;
for(int j=0,l=i+k-1;j<n;l+=k,j++)
{
if(!a[l])ok=0;
else v.pb(a[l]);
}
if(ok)
{
vi te=v;
sort(te.begin(),te.end());te.erase(unique(te.begin(),te.end()),te.end());
if(te.size()!=v.size())continue;
puts("YES");
for(int x:v)printf("%d ",x);
puts("");
return ;
}
}
puts("NO");
// for(int i=0;i<n*k+k;i++)printf("%d ",a[i]);
// puts("");
}
}ac;
int main()
{
int n,k;scanf("%d%d",&n,&k);
scanf("%s",p);
int m;scanf("%d",&m);
ac.init();
for(int i=1;i<=m;i++)
{
scanf("%s",s);
ac.ins(i);
}
ac.build();
ac.query(n,k);
return 0;
}
/********************
********************/