In Java we can use the substring() function to find position of a substring inside a String as follows:

int index = source.indexOf(substring);

However, if you are asked about an algorithm for this, here are some approaches you may use :
 

Brute force approach

In this approach, we just go through all the characters in the source and see if the target is at each position.

package com.topjavatutorial;

import java.util.Scanner;

public class FindString {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the source String");
    String source = sc.next();
    char[] src = source.toCharArray();
    System.out.println("Enter the String to search in " + source);
    String target = sc.next();
    char[] tgt = target.toCharArray();
    sc.close();
    int index = searchString(src, tgt);
    if (index != -1)
      System.out.println(target + " String found inside " + source
          + " at index : " + index);
    else
      System.out.println(target + " String not present inside " + source);
  }

  private static int searchString(char[] src, char[] tgt) {
    
    boolean found = false;

    for (int i = 0; i <= src.length - tgt.length; i++) {
      if (src[i] == tgt[0]) {
        found = true;
        for (int j = 0; j < tgt.length; j++) {
          if (src[i + j] != tgt[j])
            found = false;
        }
        if (found)
          return i;
      }
    }
    return -1;
  }
}

Output :

Enter the source String
abcdef
Enter the String to search in abcdef
cd
cd String found inside abcdef at index : 2

Enter the source String
abcd
Enter the String to search in abcd
ef
ef String not present inside abcd

Boyer–Moore string search algorithm

In Boyer-Moore algorithm compares characters starting at the target’s leftmost character. If it finds a position where the target and text don’t match, the algorithm slides the target to the right to the next position where a match might be possible.

Here is the Boyer-Moore algorithm’s java implementation (Reference : https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm)

public static int indexOf(char[] src, char[] tgt) {
          if (tgt.length == 0) {
              return 0;
          }
          int charTable[] = makeCharTable(tgt);
          int offsetTable[] = makeOffsetTable(tgt);
          for (int i = tgt.length - 1, j; i < src.length;) {
              for (j = tgt.length - 1; tgt[j] == src[i]; --i, --j) {
                  if (j == 0) {
                      return i;
                  }
              }
              // i += needle.length - j; // For naive method
              i += Math.max(offsetTable[tgt.length - 1 - j], charTable[src[i]]);
          }
          return -1;
      }
      
      private static int[] makeCharTable(char[] tgt) {
          final int ALPHABET_SIZE = Character.MAX_VALUE + 1; // 65536
          int[] table = new int[ALPHABET_SIZE];
          for (int i = 0; i < table.length; ++i) {
              table[i] = tgt.length;
          }
          for (int i = 0; i < tgt.length - 1; ++i) {
              table[tgt[i]] = tgt.length - 1 - i;
          }
          return table;
      }
      
      private static int[] makeOffsetTable(char[] tgt) {
          int[] table = new int[tgt.length];
          int lastPrefixPosition = tgt.length;
          for (int i = tgt.length - 1; i >= 0; --i) {
              if (isPrefix(tgt, i + 1)) {
                  lastPrefixPosition = i + 1;
              }
              table[tgt.length - 1 - i] = lastPrefixPosition - i + tgt.length - 1;
          }
          for (int i = 0; i < tgt.length - 1; ++i) {
              int slen = suffixLength(tgt, i);
              table[slen] = tgt.length - 1 - i + slen;
          }
          return table;
      }
      
   
      private static boolean isPrefix(char[] tgt, int p) {
          for (int i = p, j = 0; i < tgt.length; ++i, ++j) {
              if (tgt[i] != tgt[j]) {
                  return false;
              }
          }
          return true;
      }
      
      private static int suffixLength(char[] tgt, int p) {
          int len = 0;
          for (int i = p, j = tgt.length - 1;
                   i >= 0 && tgt[i] == tgt[j]; --i, --j) {
              len += 1;
          }
          return len;
      }

Please suggest any other approaches and/or improvements and we will be happy to mention them here for everyone’s reference.

© 2017, https:. All rights reserved. On republishing this post, you must provide link to original post