UVA 10100- Longest Match(dp之最长公共子序列)-白红宇

UVA 10100- Longest Match(dp之最长公共子序列)

阅读量：2029 次

发布时间：2019-04-28

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

题目地址：

题意：求两组字符串中最大的按顺序出现的相同单词数目。

思路：将字串中的连续的字母认作一个单词，依次计算出两个字符串中的单词，其中第1个字符串的单词序列为t1.word[1]…..t1.word[n]，第2个字符串的单词序列为t2.word[1]…..t2.word[m]。然后将每个单词当成一个字符，使用LCS算法计算出两个字符串的最长公共子序列，该序列的长度就是最长匹配。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-7;const int Maxn=1010;int dp[Maxn][Maxn];//str1中的前i个单词和s2中前j个单词中匹配的最多单词数。string str1,str2;struct node{ int num; string word[Maxn];}t1,t2;void devide(string s,struct node &t){ int len=s.size(); t.num=1; for(int i=0;i<1000;i++) t.word[i].clear(); for(int i=0;i
              
               ='A'&&s[i]<='Z')||(s[i]>='a'&&s[i]<='z')||(s[i]>='0'&&s[i]<='9')) t.word[t.num]+=s[i]; else t.num++; } int cnt=0; for(int i=1;i<=t.num;i++) if(!t.word[i].empty()) t.word[++cnt]=t.word[i]; t.num=cnt;}int main(){ int icase=1; while(!cin.eof()){ getline(cin,str1); devide(str1,t1); getline(cin,str2); devide(str2,t2); printf("%2d. ",icase++); if(str1.empty()||str2.empty()){ printf("Blank!\n"); continue; } for(int i=0;i<=t1.num;i++) dp[i][0]=0; for(int i=0;i<=t2.num;i++) dp[0][i]=0; for(int i=1;i<=t1.num;i++) for(int j=1;j<=t2.num;j++){ if(t1.word[i]==t2.word[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } printf("Length of longest match: %d\n",dp[t1.num][t2.num]); } return 0;}

转载地址：http://hdsaf.baihongyu.com/

你可能感兴趣的文章