题意：

给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。 并给出其在字典D下能够被理解的最长前缀的位置。理解定义为这段文章可以拆成字典里的单词。单词数≤10且长度≤10，文章数≤20且长度≤1M。

题解：

在trie上跑dp，dp[i]表示文章能否匹配到i这个位置。对于每个i，如果dp[i-1]为1，则从s[i]开始在trie上走，走过的节点数+i的dp值都置为1。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 200 6 using namespace std; 7  8 int ch[maxn][26],n,m,sz; bool d[maxn*10000],val[maxn]; char s[maxn*10000]; 9 void insert(char *s){10     int l=strlen(s+1),x=0;11     inc(i,1,l){12         if(!ch[x][s[i]-'a'])ch[x][s[i]-'a']=++sz; x=ch[x][s[i]-'a'];13     }14     val[x]=1;15 }16 int main(){17     scanf("%d%d",&n,&m); inc(i,1,n)scanf("%s",s+1),insert(s);18     inc(i,1,m){19         memset(d,0,sizeof(d)); scanf("%s",s+1); int l=strlen(s+1); d[0]=1;20         inc(i,1,l)if(d[i-1]){21             int x=0,y=i;22             while(s[y]-'a'>=0&&ch[x][s[y]-'a']){23                 x=ch[x][s[y]-'a']; if(val[x])d[y]=1; y++;24             }25         }26         while(!d[l])l--; printf("%d\n",l);27     }28     return 0;29 }
       
      
     

 

20160617