传送门

思路：

　　毒瘤的字典树！

▲主要分有两个步骤：

　　① 日常的建树。

　　② 暴力地求解。

▲日常建树：过于基础，跳过。

▲重点在于如何暴力地求解而不被卡掉（DP?不存在的）

　　可以利用区间动规的思想，枚举文章的左右端点，判断中间区间的文章是否可以被理解。

　　文章的长度几乎为 INF ，直接 N² 枚举 1~INF 显然是不可能的。

　　而看到字典里的单词长度（模式串）长度只有 10 以下，这为暴力枚举提供了一条出路。

先看一段暴力求解的代码：

for(LL j=;j<len;j++)//很暴力的枚举文章的右端点

    for(LL k=max(j-lenth_max,-INF);k<=j;k++)//枚举文章的区间左端点，（有k=max(j-lenth_max,-INF)每次最多只有枚举10个单位长度）。

        if((k==-INF||f[k])&&(find(k+,j)))

        {

            f[j]=true;ans=j+;break;

        }//注-INF = -1

　　find（ i ， j ) 用于查找 i~j 的文章中，是否能够成功匹配单词。

　　设一个 f[ j ] 表示整篇文章中，k ~ j 的文章区间能否被理解，同时要求之前文章的 f[ k ] 也要能够被理解才能更新 ans 。（因为要求求解能够被理解的文章最长前缀，不能断开）。

　　为了能够更加优化暴力，lenth_max 记录最长的单词长度。

　　有个小细节：在匹配成功一段区间后的 break ，跳出的只是枚举左端点的循环，而外层的枚举右端点的循环仍然继续。

标程：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define maxn 1000002

#define INF 1

typedef long long LL;

LL n,m,len,lenth_max,ans,ch[maxn>>][],cnt;

char s[maxn];

bool f[maxn],bo[maxn>>];

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline void insert(char *s)

{

    LL u=,len=strlen(s);

    lenth_max=max(len,lenth_max);//记录字典里最长的单词长度

    for(LL i=;i<len;i++)

    {

        LL c=s[i]-'a';

        if(!ch[u][c]) ch[u][c]=++cnt;

        u=ch[u][c];

    }

        bo[u]=;

}

inline bool find(LL l,LL r)

{

    LL u=;

    for(LL i=l;i<=r;i++)

    {

        LL c=s[i]-'a';

        if(!ch[u][c]) return false;

        u=ch[u][c];

    }

        return bo[u];

}

int main()

{

    freopen("L.in","r",stdin);

    freopen("L.out","w",stdout);

    n=read();m=read();

    for(LL i=;i<=n;i++)

    {

        scanf("%s",s);

        insert(s);

    }

    for(LL i=;i<=m;i++)

    {

        memset(f,false,sizeof(f));ans=;

        scanf("%s",s);

        LL len=strlen(s);

        for(LL j=;j<len;j++)

            for(LL k=max(j-lenth_max,-INF);k<=j;k++)

                if((k==-INF||f[k])&&(find(k+,j)))

                {

                    f[j]=true;ans=j+;break;

                }

        printf("%lld\n",ans);

    }

return ;

}

巴特西

P2292 [HNOI2004]L语言

传送门

思路：

标程：

最新文章

热门文章