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

Question

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

Here is what I still have:

 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 just practiced my algorithmic skills and got stuck.

Any tips?

Answer 1

Using only 1 loop

I made some addition to the Poran answer and it works 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; } 

Answer 2

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 } 

That 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 ultimately 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 } 

Answer 3

Tips:

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

Answer 4

This should work fine. I type 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; } 

Answer 5

This can be done in one cycle.

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