how to find what part of string exists in another string (java)

Question

String oldStr = "aaa aaa aaa aaa aaa aaa aaa aaa aaa aaa aaa bbb bbb bbb bbb";
String newStr = "bbb bbb bbb bbb ccc ccc ccc ccc ccc ccc ccc";

How do I find what part of string in newStr already exists in oldStr. I need to be able to separate new Str as below:

String newStrExistingContent = "bbb bbb bbb bbb";
String newStrNewContent = "ccc ccc ccc ccc ccc ccc ccc";

Edit: Let me make it more clear.

No part of old or new str are known. User clicks a button n logs are displayed. User does some action on application, and clicks button again, and logs are displayed again. What I am trying to do is to show new lines added to log in a didifferent color.

I hope this explanation helps.

Split them up, put each one in a `List`, iterate, remove already existing entries from there. — qqilihq, May 01 '14 at 18:25
Your problem isn't clearly defined. Does the part of `newStr` that you find in `oldStr` have to be at the beginning of `newStr`, or can it be in the middle? And if it's in the middle, what do you set `newStrNewContent` to? And do you need to find a `newStr` substring of maximal length, or just any old substring? Or does it have to be a substring at all, or (as @qqlilhq assumed) can it just be characters distributed anywhere at all in `newStr`? — ajb, May 01 '14 at 18:25
This is a big vague, even with the example. You should specify what exactly is counted as matching part, like does it have to be continuous, does it have to be at the end, what if there are multiple matching parts, etc. Also, with a SO question like this, it's usually good idea to tell what you have done so far and show some code. — hyde, May 01 '14 at 18:26
@hyde I think you meant to type "a bit vague" but your typo makes the comment more accurate... — ajb, May 01 '14 at 18:27
http://stackoverflow.com/questions/132478/how-to-perform-string-diffs-in-java might be duplicate of this. — hyde, May 11 '14 at 12:11

score 0 · Answer 1 · answered May 01 '14 at 18:29

Concerning my comment in the comments, this is how I would do it:

String oldStr = "aaa aaa aaa aaa aaa aaa aaa aaa aaa aaa aaa bbb bbb bbb bbb";
String newStr = "bbb bbb bbb bbb ccc ccc ccc ccc ccc ccc ccc";
// List<String> s1 = Arrays.asList(oldStr.split("\\s"));
// better:
Set<String> s1 = new HashSet<String>(Arrays.asList(oldStr.split("\\s")));
List<String> s2 = Arrays.asList(newStr.split("\\s"));

List<String> existing = new ArrayList<String>();
List<String> nonExisting = new ArrayList<String>();
for (String s : s2) {
    if (s1.contains(s)) {
        existing.add(s);
    } else {
        nonExisting.add(s);
    }
}

System.out.println("existing: " + existing);
System.out.println("non existing: " + nonExisting);

// existing: [bbb, bbb, bbb, bbb]
// non existing: [ccc, ccc, ccc, ccc, ccc, ccc, ccc]

If you need a string from the result Lists, you need to recombine the individual tokens, which should not be a big issue.

T.G · Answer 2 · 2014-05-01T19:31:02.553

What i would do is:

public class PartFinder {

    public static void main(String[] args) {
        String oldStr = "aaa aaa aaa aaa aaa ggg aaa aaa aaa aaa aaa bbb bbb bbb bbb";
        String newStr = "bbb bbb bbb bbb ccc ggg ccc ccc ccc ccc ccc";
        String trim = newStr;
        String tmp;
        List<String> matches = new ArrayList<>();
        while (trim.length() > 0) {
            tmp = trim;
            boolean inner = true;
            while (tmp.length() > 0 && inner) {
                if (oldStr.contains(tmp)) {
                    matches.add(tmp);
                    trim = trim.substring(tmp.length());
                    inner = false;
                }
                tmp = tmp.substring(0, tmp.length() - 1);
            }

            trim = trim.substring(1);
        }
        for (String s : matches) {
            System.out.println("Match: [" + s + "]");
        }
    }
}

Output

Match: [bbb bbb bbb bbb]
Match: [ ggg ]
Match: [ ]
Match: [ ]
Match: [ ]
Match: [ ]

As you see i modified your test strings to prove, that this will work witch parts that not only at the edge you can of course add to result list position of match (need to be calculated but it should be easy) and if you wont add only distinct matches using different type of collection, For both cases i would suggest using HashMpa<String,Integer>(matched string,start position) but that was not part of a question.

score 0 · Answer 3 · answered May 05 '14 at 14:29

Thank you everyone for taking time to look into this.

After some serious search on this forum, I found, well, what I felt was the most efficient way to get the work done:

public class StringOverlap
{
    public static String findOverlap(String s1, String s2)
    {
        if (s1 == null)
            return s2;
        if (s2 == null)
            return s1;
        int len = Math.min(s1.length(), s2.length());

        // Find the index for the end of overlapping part
        int index = -1;
        for (int i = len; i > 0; i--)
        {
            String substring = s2.substring(0, i);
            if (s1.endsWith(substring))
            {
                index = i;
                break;
            }
        }

        StringBuilder sb = new StringBuilder(s1);
        if (index < 0)
            sb.append(s2);
        else 
            if (index <= s2.length())
                sb.append(s2.substring(index));

        return sb.toString();
    }
}

how to find what part of string exists in another string (java)

3 Answers3