Java: Implement String method contains() without built-in method contains()

Question

I'm trying to implement String method contains() without using the built-in contains() method.

Here is what I have so far:

public static boolean containsCS(String str, CharSequence cs) {

    char[] chs = str.toCharArray();
    int i=0,j=chs.length-1,k=0,l=cs.length();

    //String      str = "Hello Java";
    //                   0123456789
    //CharSequence cs = "llo";

    while(i<j) {
        if(str.charAt(i)!=cs.charAt(k)) {
            i++;
        }
        if(str.charAt(i)==cs.charAt(k)) {

        }
    }

    return false;
}

I was just practicing my algorithm skills and got stuck.

Any advice?

Arawn

Why don't you look at the source code for the String.contains() method? – Desiree

Worth getting some algorithms. You may start with KMP algorithm. – Glauconite

@JBNizet The source code uses the indexOf() method but I don't want to. – Arawn

Then look at the source code of indexOf(). – Desiree

I guess that makes sense. Thanks JB Nizet. – Arawn

Answer 1

Using Only 1 Loop

I did some addition to Poran answer and It works totally fine:

 public static boolean contains(String main, String Substring) {
    boolean flag=false;
    if(main==null && main.trim().equals("")) {
        return flag;
    }
    if(Substring==null) {
        return flag;
    }

    char fullstring[]=main.toCharArray();
    char sub[]=Substring.toCharArray();
    int counter=0;
    if(sub.length==0) {
        flag=true;
        return flag;
    }

    for(int i=0;i<fullstring.length;i++) {

        if(fullstring[i]==sub[counter]) {
            counter++;
        } else {
            counter=0;
        }

        if(counter==sub.length) {
            flag=true;
            return flag;
        }

    }
    return flag;

}

Accredit

This wouldn't work in case of preceding duplicates for e.g. "eileen" and "en", to solve this add if(counter > 0){ i -= counter; } in the else part of the for loop. – Participation

There is no reason to have i-= counter. You only need to 'redo' the current iteration so just if (counter > 0) --i; will do. – Sustainer

I used code points here using your answer: #71910025 – Hamm

Answer 2

This should work fine..I am printing execution to help understand the process.

public static boolean isSubstring(String original, String str){
    int counter = 0, oLength = original.length(), sLength = str.length();
    char[] orgArray = original.toCharArray(), sArray = str.toCharArray();
    for(int i = 0 ; i < oLength; i++){
        System.out.println("counter at start of loop " + counter);
        System.out.println(String.format("comparing %s with %s", orgArray[i], sArray[counter]));
        if(orgArray[i] == sArray[counter]){
            counter++;
            System.out.println("incrementing counter " + counter);
        }else{
            //Special case where the character preceding the i'th character is duplicate
            if(counter > 0){
                i -= counter;
            }
            counter = 0;
            System.out.println("resetting counter " + counter);
        }
        if(counter == sLength){
            return true;
        }
    }
    return false;
}

Participation

Answer 3

As JB Nizet suggested, here is the actual code for contains():

2123  public boolean contains(CharSequence s) {
2124      return indexOf(s.toString()) > -1;
2125  }

And here is the code for indexOf():

1732     public int indexOf(String str) {
1733         return indexOf(str, 0);
1734     }

Which leads to:

 1752   public int indexOf(String str, int fromIndex) {
 1753       return indexOf(value, offset, count,
 1754                      str.value, str.offset, str.count, fromIndex);
 1755   }

Which finally leads to:

 1770   static int indexOf(char[] source, int sourceOffset, int sourceCount,
 1771                      char[] target, int targetOffset, int targetCount,
 1772                      int fromIndex) {
 1773       if (fromIndex >= sourceCount) {
 1774           return (targetCount == 0 ? sourceCount : -1);
 1775       }
 1776       if (fromIndex < 0) {
 1777           fromIndex = 0;
 1778       }
 1779       if (targetCount == 0) {
 1780           return fromIndex;
 1781       }
 1782   
 1783       char first  = target[targetOffset];
 1784       int max = sourceOffset + (sourceCount - targetCount);
 1785   
 1786       for (int i = sourceOffset + fromIndex; i <= max; i++) {
 1787           /* Look for first character. */
 1788           if (source[i] != first) {
 1789               while (++i <= max && source[i] != first);
 1790           }
 1791   
 1792           /* Found first character, now look at the rest of v2 */
 1793           if (i <= max) {
 1794               int j = i + 1;
 1795               int end = j + targetCount - 1;
 1796               for (int k = targetOffset + 1; j < end && source[j] ==
 1797                        target[k]; j++, k++);
 1798   
 1799               if (j == end) {
 1800                   /* Found whole string. */
 1801                   return i - sourceOffset;
 1802               }
 1803           }
 1804       }
 1805       return -1;
 1806   }

Holliehollifield

Thanks, Mr D. I know that but I just don't want to use the indexOf() method. Because using indexOf() does me no good. – Arawn

The indexOf() method you pasted is not the one used by contains(). – Desiree

@JB Nizet The one being called only contains a call to this one – Holliehollifield

No, that's not true. A CharSequence contains several characters and the indexOf() method you pasted only takes a single char as argument. – Desiree

hmmm you are right, corrected it, I think everything is included now – Holliehollifield

Answer 4

Hints:

• Use a nested loop.
• Extracting the chars to an array is probably a bad idea. But if you are going to do it, you ought to use it!
• Ignore the suggestion to use fast string search algorithms. They are only fast for large scale searches. (If you look at the code for String.indexOf, it just does a simple search ...)

Fixity

Answer 5

I came up with this:

public static boolean isSubString(String s1, String s2) {
    if (s1.length() > s2.length())
        return false;

    int count = 0;

    //Loop until count matches needle length (indicating match) or until we exhaust haystack
    for (int j = 0; j < s2.length() && count < s1.length(); ++j) {
        if (s1.charAt(count) == s2.charAt(j)) {
            ++count;
        }
        else {
            //Redo iteration to handle adjacent duplicate char case
            if (count > 0)
                --j;

            //Reset counter
            count = 0;
        }
    }

    return (count == s1.length());
}

Sustainer

Answer 6

I have recently stumbled upon this problem, and though I would share an alternative solution. I generate all the sub strings with length of the string we looking for, then push them into a hash set and check if that contains it.

 static boolean contains(String a, String b) {
    if(a.equalsIgnoreCase(b)) {
        return true;
    }
    Set<String> allSubStrings = new HashSet<>();
    int length = b.length();
    for(int i=0; i<a.length(); ++i) {
        if(i+length <= a.length()) {
            String sub = a.substring(i, i + length);
            allSubStrings.add(sub);
        }
    }
    return allSubStrings.contains(b);
}

Dysentery

Answer 7

    public static boolean contains(String large, String small) {

        char[] largeArr = large.toCharArray();
        char[] smallArr = small.toCharArray();

        if (smallArr.length > largeArr.length)
           return false;

        for(int i = 0 ; i <= largeArr.length - smallArr.length ; i++) {
            boolean result = true ;
            for(int j = 0 ; j < smallArr.length ; j++) {
                 if(largeArr[i+j] != smallArr[j]) {
                     result = false;
                     break;
                 }
                 result = result && (largeArr[i+j]==smallArr[j]); 
            }
            if(result==true) {return true;}
        }

        return false;
    }

Lorri

Answer 8

Certainly not the most efficient solution due to the nested loop, but it seems to work pretty well.

private static boolean contains(String s1, String s2) {
    if (s1.equals(s2)) return true;
    if (s2.length() > s1.length()) return false;

    boolean found = false;
    for (int i = 0; i < s1.length() - s2.length(); i++) {
        found = true;
        for (int k = 0; k < s2.length(); k++)
            if (i + k < s1.length() && s1.charAt(i + k) != s2.charAt(k)) {
                found = false;
                break;
            }
        if (found) return true;
    }
    return false;
}

Rumery

Answer 9

It can be done using a single loop.

public boolean StringContains(String full, String part) {
    long st = System.currentTimeMillis();
    if(full == null || full.trim().equals("")){
        return false;
    }
    if(part == null ){
        return false;
    }
    char[] fullChars = full.toCharArray();
    char[] partChars = part.toCharArray();
    int fs = fullChars.length;
    int ps = partChars.length;
    int psi = 0;
    if(ps == 0) return true;
    for(int i=0; i< fs-1; i++){
        if(fullChars[i] == partChars[psi]){
            psi++; //Once you encounter the first match, start increasing the counter
        }
        if(psi == ps) return true;
    }
    long et = System.currentTimeMillis()- st;
    System.out.println("StringContains time taken =" + et);
    return false;
}

Burress

This wouldn't work for cases like StringContains("fofo", "foo") as when it starts the iteration it will not reset itself after the 3rd character in the first string. What you need is to add if else after the first condition in the loop like else if(psi > 0) {psi = 0;} which will reset the value – Unveiling