Finding a string inside a string

Question

I'm trying to find a part of str1 inside str2 (two strings). Currently I have a working program however it's not exactly working correctly or using the correct logic in my opinion.

public static void main(String[] params) {
    String str1 = "blis";
    String str2 = "grisdisbliszis";
    //String str2 = "adasdsfgsdfdcx";
    System.out.println(isCommonSubstring(str1, str2));
}

public static boolean isCommonSubstring(String str1, String str2) {

    char char1, char2;
    boolean match = true;
    String check = "";

    for(int i = 0; i < str1.length(); i++) {
        char1 = str1.charAt(i);
        for(int j = 0; j < str2.length(); j++) {
            char2 = str2.charAt(j);
            if(char1 == char2) {
                check += char1;
                System.out.println("Matched!: "+str1.charAt(i)+"[Char "+i+"] <==> " // DEBUG
                    +str2.charAt(j)+"[Char "+j+"]");                                // DEBUG
                break; // Break because we've found our first match and we need to check others
            }
        }
    }
        System.out.println(check+" || "+str1);
        if(check.equals(str1)) match = true;
            else match = false;

    return match;
}

This may work but if I turn these two strings around it no longer works.

How can I improve the logic of finding a match? I tried to possibly use substring() somehow however I'm not sure how to fit it inside.

The solution I'm thinking of is possibly making if statements to compare lengths and make str2 the longer length so it's always longer and does not cause errors. But is this a decent solution?

I can only use length, substring and charAt.

Is there some reason you're not using either the built-in String function or a utility like StringUtils? — rajah9
– rajah9, Commented Oct 14, 2015 at 21:01
You should be clear if you cannot use the existing Java String API or not. Is this homework? — user1531971
– user1531971, Commented Oct 14, 2015 at 21:01
Forgot to mention I cannot use anything other than length, substring and charAt. Sorry. — Xylus
– Xylus, Commented Oct 14, 2015 at 21:04
Are you actually trying to find a common substring? If so, the name isSubstring is misleading, because it leads the readers to think your method is checking if str1 is a substring of str2. — RealSkeptic
– RealSkeptic, Commented Oct 14, 2015 at 21:04
@Xylus don't give up one your code you are close... just check the comments — Petter Friberg
– Petter Friberg, Commented Oct 14, 2015 at 21:41

Yassin Hajaj · Accepted Answer · 2015-10-14 22:30:12Z

2

The algorithm here would be the following :

Use a main loop that will stop either when the word is found, or when we've reached his length minus the length of the second string. (For example : If str1 has a length of 6 and str2 a length of 4, we know str2 does not begin at index 3 for example).
Use a second loop to check if the indexes of str2 fit somehow in str1. We check each index, one after the other inside the inner. If one of them doesn't correspond to the looped indexes of the main loop, we break from the inner loop and add one to the index of the main loop.
If the inner loop finished succesfully, we know that the word is found.

Here is a short solution possible using only charAt() and lenght():

    static boolean isCommonSubstring (String one, String two) {
        if (one.length() < two.length()){
            String tmp = one;
            one = two;
            two = tmp;
        }
        MAIN :
        for (int i = 0 ; i <= one.length()-two.length() ; i++){
            for (int j = 0 ; j < two.length() ; j++){
                if ((one.charAt(i+j) != two.charAt(j))) continue MAIN;
            }
            return true;
        }
        return false;
    }

edited Oct 14, 2015 at 22:30

answered Oct 14, 2015 at 21:18

Yassin Hajaj

22.1k10 gold badges60 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Petter Friberg Over a year ago

Maybe we help more if we do not provide own code, but help figuring out how to do it themself...., i will not down vote since you are correct

Yassin Hajaj Over a year ago

You're right Petter. That is the reason why I added the explanation.

Petter Friberg Over a year ago

Provide some notion to xylus what he need to do to make his code work, and you will get my upvote (specially since he does not wan't to be forced to pass first the longest and then the shortes... hence you have same result as xylus if you invert one and two

Petter Friberg Over a year ago

Whats does your metod return if String one = "blis" and String two = "grisdisbliszis"? see comments under question to understand..

Yassin Hajaj Over a year ago

Just invert the strings.. You can not have a string containing a greater string...

|

sam · Accepted Answer · 2015-10-14 21:12:06Z

1

String.contains() is what you are looking for.

Simple tutorial

Unless you have requirements not to use builtin functions, dont reinvent the wheel.

Example from tutorial link above:

String str1 = "tutorials point", str2 = "http://";

   CharSequence cs1 = "int";

   // string contains the specified sequence of char values
   boolean retval = str1.contains(cs1);
   System.out.println("Method returns : " + retval);

   // string does not contain the specified sequence of char value
   retval = str2.contains("_");   
   System.out.println("Methods returns: " + retval);
   }

If you want case insensitive:

str1.toLowerCase.contains(str2.toLowerCase());

EDIT turns out OP cannot use builtin functions. Will leave the answer here just in case any one else comes here who doesn't want to reinvent the wheel :)

edited Oct 14, 2015 at 21:12

answered Oct 14, 2015 at 21:01

sam

2,0232 gold badges12 silver badges13 bronze badges

2 Comments

Ceelos Over a year ago

I removed my upvote, seems like OP cannot use built in functions, so your solution (however correct) will not be helpful.

sam Over a year ago

@Ceelos. Yeah thats understandable. But someone else downvoted and just want to know if I made a mistake.

user3437460 · Accepted Answer · 2015-10-14 21:38:41Z

0

I can only use length, substring and charAt

Since you can only use those methods. This is what you can do:

//Self-defined method to check whether sub exist in str
public static boolean contains(String str, String sub){
    if(sub.length() > str.length())
        return false;    

    for(int x=0; x<= str.length() - sub.length(); x++)
        if(str.substring(x, sub.length()+x).equals(sub))                
            return true;                            
    return false;
}

EXPLANATION:

The loop will the check whether sub exist in str in the following approach:

apple (Compare "app" with "ple"  ==> does not match);
^^^    
apple (Compare "ppl" with "ple"  ==> does not match);
 ^^^    
apple (Compare "ple" with "ple"  ==> match, return true);
  ^^^

TESTING:

String a = "apple";
String b = "ple";   
System.out.println(a + " contains " + b + ": " + contains(a, b));

OUTPUT:

apple contains ple: true

edited Oct 14, 2015 at 21:38

answered Oct 14, 2015 at 21:29

user3437460

17.5k18 gold badges67 silver badges110 bronze badges

3 Comments

Petter Friberg Over a year ago

Note xylus does not like to first pass the longest and then the shortest... this is his problem... check comments...

user3437460 Over a year ago

@PetterFriberg If that is the case, he can simply swap the arguments "str" and "sub". Actually it is not even a problem at all. By improvising on my codes a little, str1 can be longer than str2 and vice versa.

Petter Friberg Over a year ago

Well if you read the comments on the question you will found out what the problem was.. I will move on have fun...

Collectives™ on Stack Overflow

Finding a string inside a string

3 Answers 3

9 Comments

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest