算法练习之从String.indexOf的模拟实现开始

String.indexOf的模拟实现，没想象中有多么高深的查找算法，就是最普通的遍历查找

思路：先找到第一个相同的字符，然后依次比较后面的字符，若都相等则表示查找成功

/**
  * 查找字符串pattern在str中第一次出现的位置
  * @param str
  * @param pattern
  * @return
  */
 public int firstIndexOf(String str, String pattern) {
   for (int i = 0; i < (str.length() - pattern.length()); i++) {
     int j = 0;
     while (j < pattern.length()) {
       if (str.charAt(i + j) != pattern.charAt(j)) break;
       j++;
     }
     if(j==pattern.length()) return i;
   }
   return -1;
 }

/**
  * 查找字符串pattern在str中最后一次出现的位置
  * @param str
  * @param pattern
  * @return
  */
 public int lastIndexOf(String str, String pattern) {
   for (int i = str.length() - pattern.length(); i >= 0; i--) {
     int j = 0;
     while (j < pattern.length()) {
       if (str.charAt(i + j) != pattern.charAt(j)) break;
       j++;
     }
     if (j == pattern.length()) return i;
   }
   return -1;
 }

/**
  * 查找字符串pattern在str中出现的位置
  * @param str
  * @param pattern
  * @return
  */
 public List<Integer> indexOf(String str, String pattern) {
   List<Integer> indexs = new ArrayList<Integer>();
   for (int i = 0; i < (str.length() - pattern.length()); i++) {
     int j = 0;
     while (j < pattern.length()) {
       if (str.charAt(i + j) != pattern.charAt(j)) break;
       j++;
     }
     if (j == pattern.length()) indexs.add(i);
   }
   return indexs;
 }

同样更常用的String.contains方法实际上就是调用的String.indexOf实现

/**
  * 判断字符串pattern在str中是否存在
  * @param str
  * @param pattern
  * @return
  */
 public boolean contains(String str, String pattern) {
   return firstIndexOf(str, pattern) != -1;
 }