poj 2264 Advanced Fruits (LCS)

谁践踏了优雅 2021-12-14 14:09 138阅读 0赞

[http://poj.org/problem?id=2264][http_poj.org_problem_id_2264]

题意：找出一个包含两个字串的最短的串；

思路：先找出两个字符串的LCS，然后构造目标字符串。例如，有两个字符串  
apple pffeach  
这两个字符串的LCS是P E  
那么分别找出P，E在两个字符串的位置，再将不属于LCS的字符插进来，就变成了：  
(a) P (pl) (ff) E (ach)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int main()
    {
         
    char a[105],b[105];
    int a1,b1,ans[105][105],i,j,aa[105],bb[105];
    while(scanf("%s%s",a+1,b+1)!=EOF)
        {
         
            a1=strlen(a+1);
            b1=strlen(b+1);
            memset(ans,0,sizeof(ans));
            memset(aa,0,sizeof(aa));
            memset(bb,0,sizeof(bb));
    for(i=1;i<=a1;i++)
    for(j=1;j<=b1;j++)
    if(a[i]==b[j])
            ans[i][j]=ans[i-1][j-1]+1;
    else
            ans[i][j]=max(ans[i-1][j],ans[i][j-1]);
            i=a1;
            j=b1;
    while(ans[i][j]!=0)
            {
         
    if(a[i]==b[j]&&ans[i][j]==ans[i-1][j-1]+1)
               {
         
                   aa[i]=1;
                   bb[j]=1;
                   i--;
                   j--;
               }
    else
    if(ans[i][j]==ans[i-1][j])
               i--;
    else
               j--;
            }
            i=1;
            j=1;
    int k=1;
    for(k=1;k<=ans[a1][b1];k++)
            {
         
    while(aa[i]==0)
              {
         
                  printf("%c",a[i]);
                  i++;
              }
    while(bb[j]==0)
              {
         
                  printf("%c",b[j]);
                  j++;
              }
              printf("%c",a[i]);
              i++,j++;
            }
    for(;i<=a1;i++)
            printf("%c",a[i]);
    for(;j<=b1;j++)
            printf("%c",b[j]);
            printf("\n");
        }
    }

转载于:https://www.cnblogs.com/LT-blogs/archive/2011/12/02/2272679.html

[http_poj.org_problem_id_2264]: http://poj.org/problem?id=2264
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/dbf5b21b8d6743fabb1aab5d2f19473e.png