求助!!!P2292 [HNOI2004] L 语言
  • 板块学术版
  • 楼主Summer_wind
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/1/15 10:05
  • 上次更新2023/10/28 12:20:29
查看原帖
求助!!!P2292 [HNOI2004] L 语言
350533
Summer_wind楼主2022/1/15 10:05

这题我用Trie的做法,全都RE了,这是为什么?大佬求助

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
const int M=1e7+10;
int ch[N][27],fail[N],len[N];
int f[M],q[N],pos[N];
int n,m,tot=1;
void charu(string s,int x)
{
    int now=1;
    for(int i=0;i<s.length();i++)
	{
        int xx=s[i]-'a';
        if(!ch[now][xx])
            ch[now][xx]=++tot;
        now=ch[now][xx];
    }
    pos[now]=x; 
}
void getfail()
{
    for(int i=0;i<26;i++) 
		ch[0][i]=1;
    int head=0,tail=1;
	int now,p;
    q[tail]=1;
	fail[1]=0;
    while(head!=tail)
	{
        now=q[++head];
        for(int i=0;i<26;i++)
		{
            if(!ch[now][i]) 
				continue;
            p=fail[now];
            while(!ch[p][i]) 
				p=fail[p]; 
            p=ch[p][i];
            fail[ch[now][i]]=p;
            q[++tail]=ch[now][i];
        }
    }
}
int getres(string s)
{
    memset(f,0,sizeof(f));
    f[0]=1;
    int ans=0;
    int now=1;
    for(int i=0;i<s.length();i++)
	{
        int x=s[i]-'a';
        while(!ch[now][x])
			now=fail[now];
        now=ch[now][x];    
        for(int j=now;j;j=fail[j])
            f[i+1]|=f[i-len[pos[j]]+1];
    }
    for(int i=s.length();~i;i--) 
        if(f[i])
        {
            printf("%d\n",i);
			break;
		}
}
int main()
{
    scanf("%d %d",&n,&m);
    string ss;
    for(int i=1;i<=n;i++)
	{
        cin>>ss;
        len[i]=ss.length();
        charu(ss,i);
    }
    fail[0]=0;
    getfail();
    for(int i=0;i<m;i++)
	{
        cin>>ss;
        getres(ss);
    }
	return 0;
}
2022/1/15 10:05
加载中...