ncpc2016B cf-gym-101550B

大概知道是字典树DP，然而没有想出来，涛爷还是强啊，在我写A题的时候连切一大把题。

根据题意重复覆盖部分前面的单词优先级更大，所以建字典树新节点的时候才要记录一些值，保证能知道当前点能tap到哪个单词

建字典树的时候，第k条字典单词，记录rc[k]表示第k个单词最深度最小的属于他的点是哪个，id[u]表示编号为u的点

是属于第几个单词的，top[u]表示当前节点的单词最上面的属于这个单词的节点到哪，dp[u]表示从到u点需要走多少步

吧单词的字典树建好以后，在判断一串字符串最短编辑距离时，如果已经匹配到字典树中没有的节点了，那么就只能从上到下一个字母一个字母地加了。而如果还在字典树上，那么要么从当前点u直接加到尾，要么就从top[u]按一下tap到该单词最底下再一个一个减回来。

整个dp的感觉有点像字典树上的kmp，先对模式串自己求dp数组，再对文本串进行dp

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int maxn=(1<<20)+5;
typedef long long LL;
const double eps=1e-8;
int n,m,root,cnt,ans,L[maxn],id[maxn];
char s[maxn];
int dp[maxn],dep[maxn],top[maxn],rc[maxn];
int T[maxn][26];

inline int newnode()
{
    ++cnt;
    memset(T[cnt],0,sizeof(T[cnt]));
    dp[cnt]=0;
    dep[cnt]=0;
    return cnt;
}

inline void Ins(char *s,int len,int k)
{
    int u=root;
    while(*s)
    {
        int c=*s-'a';
        if(!T[u][c])
        {
            T[u][c]=newnode();
            if(!rc[k])rc[k]=T[u][c];
            id[T[u][c]]=k;
            top[T[u][c]]=rc[k];
            dep[T[u][c]]=dep[u]+1;

            int i=T[u][c];
            if(i==top[i])dp[i]=dp[u]+1;
            else dp[i]=dp[top[i]]+min(dep[i]-dep[top[i]],1+len-dep[i]);
        }
        u=T[u][c];
        ++s;
    }
}

inline void Find(char *s,int len)
{
    int u=root;
    //bool ok=1;
    while(*s)
    {
        int c=*s-'a';
        if(!T[u][c])
        {
            ans=min(ans,dp[u]+len-dep[u]);
            //ok=0;
            break;
        }
        u=T[u][c];
        ans=min(ans,min(dp[u]+len-dep[u],dp[top[u]]+1+L[id[u]]-dep[u]+len-dep[u]));
        ++s;
    }
    //if(ok)ans=min(ans,dp[u]);
}

int main()
{
	int ok=0;
    while(~scanf("%d%d",&n,&m))
    {
    	if(ok)printf("\n");
    	ok++;
        cnt=0;
        memset(T[0],0,sizeof(T[0]));
        memset(rc,0,sizeof(rc));
        memset(top,0,sizeof(top));
        memset(L,0,sizeof(L));
        memset(id,0,sizeof(id));
        for(int i=1;i<=n;++i)
        {
            scanf("%s",s+1);
            int len=strlen(s+1);
            L[i]=len;
            Ins(s+1,len,i);
        }
        for(int i=1;i<=m;++i)
        {
            scanf("%s",s+1);
            int len=strlen(s+1);
            ans=len;
            Find(s+1,len);
            printf("%d\n",ans);
        }
        //for(int i=1;i<=cnt;++i)
            //printf("id= %d dep= %d  dp= %d top= %d\n",i,dep[i],dp[i],top[i]);
    }
    return 0;
}