Loading...

HNOI2004 L语言

check评论:0 条 remove_red_eye浏览量:500 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-26

qwq
字典树裸题qwq
qwq
code:

#include <bits/stdc++.h>
#define N 2000010
using namespace std;
int n,m,len=0;
char s[N];
int longest[N],h=0;
int child[10000][26],is[10000]; 
void insert()
{
    int p=0;
    int l=strlen(s);
    len=max(len,l);
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!child[p][c])
        {
            h++;
            child[p][c]=h;
        } 
        p=child[p][c];
    }
    is[p]=1;
}
int find(int head,int tail)
{
    int p=0;
    for(int i=head;i<=tail;i++)
    {
        int c=s[i]-'a';
        if(!child[p][c])
        {
            return 0;
        }
        p=child[p][c];
    }
    return is[p];
}
void clear()
{
    memset(child,0,sizeof(child));
    memset(is,0,sizeof(is));
}
int main()
{
    scanf("%d%d",&n,&m);
    clear();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        insert();
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        memset(longest,0,sizeof(longest));
        int l=strlen(s),ans=0;
        for(int j=0;j<l;j++)
        {
            int qwq=max(j-len,-1);
            for(int k=qwq;k<=j;k++)
            {
                if((k==-1||longest[k]))
                {
                    if(find(k+1,j))
                    {
                        longest[j]=1;
                        ans=j+1;
                        break;
                    } 
                }
            }
        }       
        printf("%d\n",ans);
    }
    return 0;
}

chevron_left NOIP2018游记
字典树 洛谷P2580 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名