100723H Obfuscation-白红宇

100723H Obfuscation

阅读量：7043 次

发布时间：2019-06-28

本文共 1258 字，大约阅读时间需要 4 分钟。

题目大意

给你一个包含n 个单词的字典，给你一篇文章，文章包括若干词典里的单词，把句子里的空格都去掉，单词的首位字母都不变，中间的字符集为乱序，问能否恢复这篇文章，使得单词都是词典里的单词，如果有唯一解，输出唯一解。

分析

可以将将一段字符串哈希来确定这段字符串的字母组成，在记录每一段的首字母和尾字母，这样便可以将整段字符表示出来了，在进行完预处理之后我们进行dp，用dpi表示i+1到m这一段的字符可以由先有字母表组成几个。最后如果dp0有0个则代表无法组成，大于1则有歧义，等于一则根据之前记录的nxt数组和每一段字符对应的编号将答案输出。详见代码。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define sp cout<<"---------------------------------------------------"<
                   
                    mp[28][28];multiset
                    
                     HASH[28][28];int main(){ srand(time(0)+1010101); int n,m,i,j,t; for(i=0;i<28;i++) wsh[i]=(uli)rand()*rand()*rand()*rand()*rand()*rand()*rand()*rand(); scanf("%d",&t); while(t--){ for(i=0;i<26;i++) for(j=0;j<26;j++){ HASH[i][j].clear(); mp[i][j].clear(); } scanf("%s",bs); scanf("%d",&n); m=strlen(bs); for(i=1;i<=n;i++){ scanf("%s",s[i]); len[i]=strlen(s[i]); uli hsh=0; for(j=0;j
                     
                      =0;i--){ uli hsh=0; for(j=i;j
                      
                       0&&dp[j+1]){ dp[i]+=x*dp[j+1]; nxt[i]=j+1; } } dp[i]=min(dp[i],2); } if(dp[0]==0)puts("impossible"); else if(dp[0]>1)puts("ambiguous"); else { for(i=0;i

转载于:https://www.cnblogs.com/yzxverygood/p/9346300.html

你可能感兴趣的文章