Merge two strings with common starting and ending substrings

Tag: string , algorithm , substring Author: durant11 Date: 2012-02-16

I have two strings the ending substring of first is the starting substring of the second,ex

string left : ONESTRING
string right : STRINGTWO

I have to merge them so that the resulting string is

result string : ONESTRINGTWO

The length of the common substring is not known in advance. If the starting and ending strings are not common, i need to return the concatenation of the strings.

This is what i am doing currently.

for(int i = 1;i< left.length();i++) {
        //substring of length "i" from last of left string
        string temp = left.substr(left.length() -1 -i,i);
        if(temp.length() < right.length()) {
            //check if the right string starts with the above substring 
            if (strncmp(right.c_str(), temp.c_str(), strlen(temp.c_str())) == 0 ) {
                // common substring found, save this result 
                found =  true;
                result = left.substr(0,left.length()-i-1) + right;
            }

        }
    }

if(found == true) {
    return result;
} else {
    return left + right;
}

I would be thankful for any pointers to a simpler implementation (in any language ).

check answer for Java and let me know if you have any questions...

Best Answer

By smart use of pointer arithmetic, you can skip the calls to substr (which do allocation) and strlen (which take O(n) time in the length of the string).

std::string concat(std::string const &left, std::string const &right)
{
    size_t n = left.length();
    for (size_t i=0; i<n; i++)
        if (std::strncmp(left.c_str() + i, right.c_str(), n - i) == 0)
            return left + (right.c_str() + n - i);

    return left + right;
}

comments:

Thanks for the answers

Other Answer1

Try Below... Tested and it is working in JAVA...

public class FindString {
    public static void main(String[] args) {
    String myString01 = "OneString";
    String myString02 = "StringTwo";

    String commonString = "";
    for (int i = 0; i < myString01.length(); i++) {
        if (myString02.indexOf(myString01.substring(i)) >= 0) {
        commonString = myString01.substring(i);
        break;
        }
    }

    System.out.println("common is " + commonString);

    String firstPart = myString01.substring(0, myString01.indexOf(commonString));
    String secondPart = myString02.substring(myString02.indexOf(commonString) + commonString.length());
    String finalString = firstPart + commonString + secondPart;

    System.out.println("Final String of " + myString01 + " & " + myString02 + " is " + finalString);
    }
}

Note

If you want to make them lowercase and then compare, then use .toLowerCase().

Update 1

Output that I have is

common is String
Final String of OneString & StringTwo is OneStringTwo

And I believe this is what you want...

Update 2

Some advanced over above is as below.

public class FindString {
    public static void main(String[] args) {
    String myString01 = "StringOne";
    String myString02 = "TwoString";

//        String myString01 = "StringOne";
//        String myString02 = "StringTwo";


//        String myString01 = "OneString";
//        String myString02 = "TwoString";

//        String myString01 = "OneString";
//        String myString02 = "StringTwo";

    System.out.println("First String is  = " + myString01);
    System.out.println("Second String is = " + myString02);

    String commonString = "";
    for (int i = 0; i < myString01.length(); i++) {
        if (myString02.indexOf(myString01.substring(i)) >= 0) {
        commonString = myString01.substring(i);
        break;
        }
    }

    if (commonString.isEmpty()) {
        for (int i = 0; i < myString02.length(); i++) {
        if (myString01.indexOf(myString02.substring(i)) >= 0) {
            commonString = myString02.substring(i);
            break;
        }
        }

    }

    String firstPart;

    if (myString01.indexOf(commonString) > 0) {
        firstPart = myString01.substring(0, myString01.indexOf(commonString));
    } else {
        firstPart = myString01.substring(myString01.indexOf(commonString) + commonString.length());
    }

    String secondPart;

    if (myString02.indexOf(commonString) > 0) {
        secondPart = myString02.substring(0, myString02.indexOf(commonString));
    } else {
        secondPart = myString02.substring(myString02.indexOf(commonString) + commonString.length());
    }

    System.out.println("First Part  = " + firstPart);
    System.out.println("Second Part = " + secondPart);
    System.out.println("Common Part = " + commonString);

    String finalString = firstPart + commonString + secondPart;

    System.out.println("Final String of " + myString01 + " & " + myString02 + " is " + finalString);
    }
}

Other Answer2

Try this , it works for me

public Void FindString (string left ,string right)
{
int i=0;
string result = string.Empty;

for( i = right.Length ; i>=0;i--)
{
   if(left.Contains(right.Substring(0,i)))
   {
     break;
   }
}

if(i<right.Length)
{
    result =right.Substring(0,i);
}
return  left.Replace(result,"") + result +right.Replace(result,""); 
}