28 - Find the Index of the First Occurrence in a String

 JAVA

• class Solution {
      public int strStr(String haystack, String needle) {
          if ("".equals(needle)) {
              return 0;
          }
  
          int len1 = haystack.length();
          int len2 = needle.length();
          int p = 0;
          int q = 0;
          while (p < len1) {
              if (haystack.charAt(p) == needle.charAt(q)) {
                  if (len2 == 1) {
                      return p;
                  }
                  ++p;
                  ++q;
              } else {
                  p -= q - 1;
                  q = 0;
              }
  
              if (q == len2) {
                  return p - q;
              }
          }
          return -1;
      }
  }
  
  /////////
  
  func strStr(haystack string, needle string) int {
  	n, m := len(haystack), len(needle)
  	sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
  	multi := 1
  	for i := 0; i < m; i++ {
  		target = (target*256%mod + int(needle[i])) % mod
  	}
  	for i := 1; i < m; i++ {
  		multi = multi * 256 % mod
  	}
  
  	for ; right < n; right++ {
  		sha = (sha*256%mod + int(haystack[right])) % mod
  		if right-left+1 < m {
  			continue
  		}
  		if sha == target && haystack[left:right+1] == needle {
  			return left
  		}
  		sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
  		left++
  	}
  	return -1
  }

C++

• class Solution {
  private:
      vector<int> Next(string str) {
          vector<int> n(str.length());
          n[0] = -1;
          int i = 0, pre = -1;
          int len = str.length();
          while (i < len) {
              while (pre >= 0 && str[i] != str[pre])
                  pre = n[pre];
              ++i, ++pre;
              if (i >= len)
                  break;
              if (str[i] == str[pre])
                  n[i] = n[pre];
              else
                  n[i] = pre;
          }
          return n;
      }
  
  public:
      int strStr(string haystack, string needle) {
          if (0 == needle.length())
              return 0;
  
          vector<int> n(Next(needle));
  
          int len = haystack.length() - needle.length() + 1;
          for (int i = 0; i < len; ++i) {
              int j = 0, k = i;
              while (j < needle.length() && k < haystack.length()) {
                  if (haystack[k] != needle[j]) {
                      if (n[j] >= 0) {
                          j = n[j];
                          continue;
                      } else
                          break;
                  }
                  ++k, ++j;
              }
              if (j >= needle.length())
                  return k - j;
          }
  
          return -1;
      }
  };