题意:给你一个模式串和一堆长度相同的不相同的匹配串,问是否有一个方案可以让这个模式串由这些匹配串首尾相连组成,每个串只能出现一次.
思路:还是比较简单的,显然模式串每个位置最多匹配一个匹配串,因为所有的匹配串严格不同,每个位置有没有匹配哪个匹配串用ac自动机很容易就能跑出来,然后枚举一下位置就ok,还有模式串应该在开头加上尾部的一些字符,因为要求的是这个模式串要看成一个环.
#include <bits/stdc++.h>
using namespace std;
char aim[];
int pos[];
char temp[];
int total;
struct Root
{
Root *next[];
int count;
Root *fail;
Root()
{
for(int i=; i<; i++)
next[i]=NULL;
fail=NULL;
count=;
}
};
queue<Root *>q;
class AC_auto
{
public:
AC_auto();
void insert(char object[],int num);
void ac_auto();
void match(char aim[]);
private:
Root *root;
};
AC_auto::AC_auto()
{
root=new Root();
}
void AC_auto::insert(char object[],int num)
{
int len=strlen(object);
Root *temp=root;
for(int i=; i<len; i++)
{
if(temp->next[object[i]-'a']==NULL)
{
Root *temp1=new Root();
temp->next[object[i]-'a']=temp1;
}
temp=temp->next[object[i]-'a'];
}
temp->count=num;
}
void AC_auto::ac_auto()
{
while(!q.empty())q.pop();
q.push(root);
Root *temp1,*temp2;
while(!q.empty())
{
temp1=q.front();
q.pop();
for(int i=; i<; i++)
{
if(temp1->next[i])
{
if(temp1==root)
temp1->next[i]->fail=root;
else
{
temp2=temp1->fail;
while(temp2)
{
if(temp2->next[i])
{
temp1->next[i]->fail=temp2->next[i];
break;
}
temp2=temp2->fail;
}
if(temp2==NULL)
temp1->next[i]->fail=root;
}
q.push(temp1->next[i]);
}
}
}
}
void AC_auto::match(char aims[])
{
int len=strlen(aims);
Root *temp1,*temp=root;
for(int i=; i<len; i++)
{
if(aims[i]>'z'||aims[i]<'a')
{
temp=root;
continue;
}
while(temp->next[aims[i]-'a']==NULL&&temp!=root)
temp=temp->fail;
temp=temp->next[aims[i]-'a'];
if(!temp)temp=root;
if(temp->count)
pos[i]=temp->count;
}
}
bool sign[];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",aim+k);
for(int i=;i<k;i++)
aim[i]=aim[(n+)*k-k+i];
AC_auto *ac_auto=new AC_auto();
int g;
scanf("%d",&g);
for(int i=;i<=g;i++)
{
scanf("%s",temp);
ac_auto->insert(temp,i);
}
ac_auto->ac_auto();
ac_auto->match(aim);
for(int i=k;i<*k;i++)
{
for(int j=i;j<n*k+k;j+=k)
{
if(pos[j]==)
break;
else if(sign[pos[j]])
break;
sign[pos[j]]=true;
if(j+k>=n*k+k)
{
printf("YES\n");
for(int j=i;j<n*k+k;j+=k)
printf("%d ",pos[j]);
return ;
}
}
for(int j=i;j<n*k+k;j+=k)
{
if(pos[j]==)
break;
sign[pos[j]]=false;
}
}
printf("NO\n");
return ;
}