The second day of intensive training at Nanjing Foreign Language School.
今天讲AC自动机
不,今天讲自动WA机
为什么我的第二题过不了???
第三题代码
#include
using namespace std;
int n,m,tr[11000][26],tot,fail[11000],dp[1100][400],p[11000];
char s[11000];
void add(char *s){
int u=0;
for(int i=0;s[i];i++)
{
int c=s[i]-'A';
if(!tr[u][c]) tr[u][c]=++tot;
u=tr[u][c];
}
p[u]++;
}
queue q;
void build(){
for(int i=0;i<3;i++)
{
if(tr[0][i]) q.push(tr[0][i]);
}
while(q.size())
{
int u=q.front();
q.pop();
for(int i=0;i>n>>m;
for(int i=1;i>s;
add(s);
}
memset(dp,-1000000,sizeof(dp));
build();
dp[0][0]=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<=tot;j++)
{
for(int k=0;k<3;k++)
{
int h=tr[j][k];
dp[i+1][h]=max(dp[i+1][h],dp[i][j]+p[h]);
}
}
}
int res=0;
for(int i=0;i<tot;i++)
{
res=max(res,dp[m][i]);
}
cout<<res;
return 0;
}