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?

Solution 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;

}

Solution 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;
}

Solution 3

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 ...)

Solution 4

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   }

Solution 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());
}

View more solutions

Comments

[danksim]

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

[JB Nizet]

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

[0x6C38]

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

[JB Nizet]

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

[0x6C38]

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

[Sarp Kaya]

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

[Arif Nadeem]

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.

[Mo Beigi]

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

[Tugalsan Karabacak]

I used code points here using your answer: stackoverflow.com/questions/71909525/…