首页 > ACM题库 > HDU-杭电 > HDU 3252-Code Merging[解题报告]HOJ
2014
03-13

HDU 3252-Code Merging[解题报告]HOJ

Code Merging

问题描述 :

Background

Version control is the art of managing changes to information. It has long been a critical tool for programmers, who typically spend their time making small changes to software and then undoing those changes the next day. But the usefulness of version control software extends far beyond the bounds of the software development world. Anywhere you can find people using computers to manage information that changes often, there is room for version control.

Some version control systems are also software configuration management (SCM) systems. These systems are specifically tailored to manage trees of source code, and have many features that are specific to software development-such as natively understanding programming languages, or supplying tools for building software.

One nice feature that many SCM systems provide is called "Code Merging", which allows a code to be modified simultaneously by two coders. As long as they work on DIFFERENT parts of the code, modifications could be merged gracefully.

Consider the following code:

void idle(){}
void goShoppingWithGirlFriend(){…}
void playGames(){…}
int main()
{
if (today.isSunday())
idle();
}

Mr. T added a function "greeting Pan Xi" by changing the original code into:

void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){…}
void playGames(){…}
int main()
{
if (today.isSunday())
idle();
}

At the same time, Mr. L added a function "greeting Xue Xiaoyuan" by changing the original code into:

void idle(){}
void goShoppingWithGirlFriend(){…}
void playGames(){…}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
if (today.isSunday())
idle();
}

Note that two modifications are made in different parts of the code, so smart SCMs can happily merge them, preserving both new functionalities:

void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){…}
void playGames(){…}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
if (today.isSunday())
idle();
}

Amazing, right?

But life’s not always easy. If someone else changed the last part into:

if(today.isSunday())
playGames();

And another anonymous coder wrote the following:

if(today.isSunday())
goShoppingWithGirlFriend();

I bet no SCM in the world really knows what to do – it totally depends on the coder, though Mr. T and Mr. L both prefer the latter.

Task

In this problem, your task is to implement the following code merging algorithm:

* Each line of a code is considered as an atomic element, so the algorithm actually takes as input two sequences A and B.
* Calculates the longest common subsequence (LCS) of these two sequences, denoted by (a1,b1), (a2,b2), …, (ak,bk), i.e. The ai-th line of code A matches the bi-th line of code B, and k is the length of the LCS. By "matching", two lines should be exactly the same, including whitespace characters.
* By the definition of LCS, a1<a2<a3<…<ak, b1<b2<b3<…<bk, which are called match points. We split both sequences into k+1 so-called diff-sections by their own match points, then merge each pair of diff-sections one by one.
* Print the merged diff-sections, separated by the lines in the LCS.

IMPORTANT: in order for the result to be stable, the integer sequence (a1, b1, a2, b2, …, ak, bk) should be lexicographically smallest. Thus, the output of the algorithm is always unique.

For people who’re still confused, here is some more technical information: let M[i] be the i-th match-point, i.e., M[i] = A[ai] = B[bi], DA[i] be the i-th diff-section of A, i.e. DA[i] = {A[ai-1+1 ... ai-1]} (note that a0=0, ak+1=len(A)+1). It’s not hard to see that code A can be rewritten as: DA[1], M[1], DA[2], M[2], …, DA[k], M[k], DA[k+1]. We can define DB[i] similarly.

With these symbols, we can easily express the final output of this problem as:

merge(DA[1],DB[1])
M[1]
merge(DA[2],DB[2])
M[2]
merge(DA[3],DB[3])
M[3]

M[k]
merge(DA[k+1],DB[k+1])

Where merge(DA[i],DB[i]) is calculated as follows:

* If one of DA[i] and DB[i] is empty, return the other (though it can be again empty)
* otherwise, report a conflict, showing content of the diff-sections in both codes (see sample output below).

输入:

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains code A followed by code B. Both codes end with a line containing 9 character #CODE-END (excluding the newline character). Each code contains at most 1000 lines, each line contains no more than 200 characters, and is guaranteed to be followed by a newline character.

输出:

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains code A followed by code B. Both codes end with a line containing 9 character #CODE-END (excluding the newline character). Each code contains at most 1000 lines, each line contains no more than 200 characters, and is guaranteed to be followed by a newline character.

样例输入:

2
void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
int main()
{
    if (today.isSunday())
        idle();
}
#CODE-END
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
    if (today.isSunday())
        idle();
}
#CODE-END
int main()
{
    if(today.isSunday())
        playGames();
}
#CODE-END
int main()
{
    if(today.isSunday())
        goShoppingWithGirlFriend();
}
#CODE-END

样例输出:

Case 1:
void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
    if (today.isSunday())
        idle();
}

Case 2:
int main()
{
    if(today.isSunday())
//**** CONFLICT STARTS ****//
//code in A:
        playGames();
//code in B:
        goShoppingWithGirlFriend();
//***** CONFLICT ENDS *****//
}

#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <cstring>
#include <set>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX=1005,INF=1<<30;
const string END="#CODE-END";

int len;
map<string,int> mymap;
map<string,int>::iterator ite;

vector<string> A,B;

int cnt;
int f[MAX][MAX];
int ma[MAX],mb[MAX];
vector<int> a,b;
int Test;

void read(vector<string> &t,vector<int> &arr){

    string s;
    while(getline(cin,s)){
        if(s==END)
            break;
        ite=mymap.find(s);
        if(ite==mymap.end())
            mymap[s]=len++;
//        cout<<"LEN: "<<s<<" "<<mymap[s]<<endl;

        t.push_back(s);
        arr.push_back(mymap[s]);
    }

//    for(int i=0;i<(int)arr.size();i++)
//        cout<<"T:  "<<arr[i]<<endl;


    return ;
}

void createM(){

    int n1=(int)a.size()-1,n2=(int)b.size()-1;
//    cout<<"n1:n2 "<<n1<<" "<<n2<<endl;
//    f[0][0]=0;
//    for(int i=0;i<=n1;i++) f[i][0]=0;
//    for(int i=0;i<=n2;i++) f[0][i]=0;
    memset(f,0,sizeof(f));

    for(int i=n1;i>=1;i--){
        for(int j=n2;j>=1;j--){
            if(a[i]==b[j])
                f[i][j]=f[i+1][j+1]+1;
            else
                f[i][j]=max(f[i+1][j],f[i][j+1]);
        }
    }

//    cout<<f[n1][n2]<<endl;
//    if(Test==0){
//        for(int i=0;i<=n1;i++)
//            cout<<"a: "<<a[i]<<endl;
//
//        for(int i=0;i<=n2;i++)
//            cout<<"b: "<<b[i]<<endl;
//    }

//    int i=1,j=1;
    int L=f[1][1];
    cnt=f[1][1];
//    while(L<f[1][1]){
////        if(i>n1||j>n2)
////            while(1) ;
//        if(a[i]==b[j]){
//            ma[L]=(i++)-1;
//            mb[L]=(j++)-1;
//            ++L;
//        }
//        else if(f[i+1][j]<f[i][j+1])
//            ++j;
//        else
//            ++i;
//    }

    int x = -1,c=0;
    for(int i = 1; i<=n1; i++)
    {
        for(int j = 1; j<= n2; j++)
        {
            if(a[i] == b[j] && f[i][j] == L && j > x)
            {
                x = j;
                L--;
//                record[cnt][0] = i, record[cnt][1] = j;
                ma[c]=i-1;
                mb[c]=j-1;
                x = j;
                c++;
                break;
            }
        }
    }
//    cout<<"DSA: "<<n1<<" "<<n2<<endl;
//    cout<<"ASD: "<<i<<" "<<j<<endl;

//    cout<<"CNTTTTTTTTTTTTT: "<<cnt<<endl;
//    for(int i=0;i<cnt;i++)
//        cout<<ma[i]<<" "<<mb[i]<<endl;

    return ;
}

struct DD{
    bool isM;
    int b,e;
};
DD DA[MAX*3],DB[MAX*3];

void cut(){
//    cout<<"CNT: "<<cnt<<endl;
    int front=0,rear=0;

    int len=0;
    for(int i=0;i<2*cnt;i++,len++){
        rear=ma[len];
        if(front<rear){
            DA[i].isM=0;
            DA[i].b=front;
            DA[i].e=rear-1;
        }
        else {
            DA[i].isM=0;
            DA[i].b=-1;
            DA[i].e=-1;
        }

        //plus M[];
        ++i;
        DA[i].isM=1;
        DA[i].b=ma[len];
        DA[i].e=ma[len];
        front=ma[len]+1;

    }
    rear=(int)A.size();

    if(front<rear){
        DA[cnt*2].isM=0;
        DA[cnt*2].b=front;
        DA[cnt*2].e=rear-1;
    }
    else {
        DA[cnt*2].isM=0;
        DA[cnt*2].b=-1;
        DA[cnt*2].e=-1;
    }

    front=rear=0;
    len=0;
    for(int i=0;i<2*cnt;i++,len++){
        rear=mb[len];
        if(front<rear){
            DB[i].isM=0;
            DB[i].b=front;
            DB[i].e=rear-1;
        }
        else {
            DB[i].isM=0;
            DB[i].b=-1;
            DB[i].e=-1;
        }

        //plus M[];
        ++i;
        DB[i].isM=1;
        DB[i].b=mb[len];
        DB[i].e=mb[len];
        front=mb[len]+1;

    }
    rear=(int)B.size();

    if(front<rear){
        DB[cnt*2].isM=0;
        DB[cnt*2].b=front;
        DB[cnt*2].e=rear-1;
    }
    else {
        DB[cnt*2].isM=0;
        DB[cnt*2].b=-1;
        DB[cnt*2].e=-1;
    }

//    cout<<"TES: "<<endl;
//    for(int i=0;i<2*cnt+1;i++){
//        cout<<DB[i].b<<" "<<DB[i].e<<" ";
//        if(DB[i].isM)
//            cout<<"YES"<<endl;
//        else
//            cout<<"NO"<<endl;
//
//    }

    return ;
}

void output(){

    for(int i=0;i<2*cnt+1;i++){

        if(DA[i].isM)
            cout<<A[DA[i].b]<<endl;
        else if(DA[i].b==-1&&DA[i].e==-1){
            if(DB[i].b==-1&&DB[i].e==-1)
                continue;
            else{
                for(int j=DB[i].b;j<=DB[i].e;j++){
                    cout<<B[j]<<endl;
                }
            }
        }
        else if(DB[i].b==-1&&DB[i].e==-1){
            if(DA[i].b==-1&&DA[i].e==-1)
                continue;
            else{
                for(int j=DA[i].b;j<=DA[i].e;j++){
                    cout<<A[j]<<endl;
                }
            }
        }
        else {
            cout<<"//**** CONFLICT STARTS ****//"<<endl
                <<"//code in A:"<<endl;
            for(int j=DA[i].b;j<=DA[i].e;j++){
                cout<<A[j]<<endl;
            }
            cout<<"//code in B:"<<endl;
            for(int j=DB[i].b;j<=DB[i].e;j++){
                cout<<B[j]<<endl;
            }
            cout<<"//***** CONFLICT ENDS *****//"<<endl;
        }

    }
    return ;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("i.txt", "r", stdin);
#endif
//    freopen("comehome.in","r",stdin);
//    freopen("comehome.out","w",stdout);

    int test=1;
    cin>>Test;
    cin.ignore();
    while(Test--){

        cout<<"Case "<<test++<<":"<<endl;

        len=0;
        mymap.clear();
        A.clear();B.clear();
        a.clear();b.clear();
        a.push_back(-1);b.push_back(-1);

        read(A,a);
        read(B,b);

        createM();

        cut();

        output();
        cout<<endl;
    }
    return 0;
}

  1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts