*
The moose likes Beginning Java and the fly likes Best way to figure out overlapping of strings Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Best way to figure out overlapping of strings" Watch "Best way to figure out overlapping of strings" New topic
Author

Best way to figure out overlapping of strings

Binu K Idicula
Ranch Hand

Joined: Jul 11, 2002
Posts: 99
Hi,

I have 2 Strings. Is there a regex way of finding out the overlapping part?


String str1 = "AB-CD";
String str2 = "CH-EF"

Now C is the overlapping part. I did it with tokenizer and with a custom algorithm, going one by one. But Is there a simple way out?

regards
Binu K Idicula
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
Moving to another forum since this really more of a question that a Diversion. The Click Here link will take you to its new home.

Eric
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38100
    
  22
That isn't really an overlap; if you had ABCD and CDEF then the overlap would be CD.

You can try putting one String into a regular expression inside [] and the seeing whether you can match the other. But then you would get ABCD matching FEDC on the DC. In the case you mention you would also have problems with the - because it is a special character.

There is lots and lots of information about regular expressions; the Java Tutorials is a good place to start.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
Another important question would be what is considered overlap? If you have:

"abcde" and "cdfg" does the "cd" overlap?
"abcde" and "fbcg" does the "bc" overlap?


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Bill Shirley
Ranch Hand

Joined: Nov 08, 2007
Posts: 457
are you asking for "greatest common substring" rather than an "overlap"?


Bill Shirley - bshirley - frazerbilt.com
if (Posts < 30) you.read( JavaRanchFAQ);
Binu K Idicula
Ranch Hand

Joined: Jul 11, 2002
Posts: 99
"abcde" and "cdfg" does the "cd" overlap? - YES
"abcde" and "fbcg" does the "bc" overlap? - YES

are you asking for "greatest common substring" rather than an "overlap"? - YES, precisely.

Any thoughts?
Piet Verdriet
Ranch Hand

Joined: Feb 25, 2006
Posts: 266
Wikipedia has a nice article about this:
http://en.wikipedia.org/wiki/Longest_common_substring_problem
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
Here's a link to the Wikipedia article on the subject. It contains a pseudocode algorithm that you might be able to adapt. It's a starting point if nothing else.


edit: 2 minutes too slow!
[ December 03, 2008: Message edited by: Garrett Rowe ]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38100
    
  22
Originally posted by Garrett Rowe:
edit: 2 minutes too slow!


That happens to me all the time whenever Rob Prime is online!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Best way to figure out overlapping of strings
 
Similar Threads
String Numeric Comparator
Date Range Compare:Overlaps
overlapping dates
automatic Externalizing Strings from JSP Files.
Best way to figure out overlapping of strings