/**
 * 由于模式字符串的长度是一定的，那么在进行匹配的时候可以在目标字符串中进行一次循环遍历
 * 当模式串的hash值和目标串中长度与模式串相同的子串的hash值相等时该子串就有可能是要求解
 * 的子串，然后进行一次全匹配即可判断出结果；另外在目标串中进行hash值的计算时，由于第
 * i+1个子串的hash值与第i个子串的hash值有一定的关系，因而可以迅速计算出结果
 */
public class Solution {
  public int getFirstMatchedString(String goal, String pattern) { // abcdef  def
    if (goal.length() < pattern.length()) {
      return -1;
    }

    int hashGoal = computeHashCode(goal.substring(0, pattern.length()));
    int hashPattern = computeHashCode(pattern);

    for (int i = 0; i <= goal.length() - pattern.length(); i++) {
      if (hashGoal == hashPattern && goal.substring(i, i + pattern.length()).equals(pattern)) {
        return i;
      }
      hashGoal = computeHashCode(goal, i + 1, pattern.length(), hashGoal);
    }

    return -1;
  }

  private int computeHashCode(String goal, int index, int k, int oldHashCode) {
    return 31 * oldHashCode + goal.charAt(index - 1 + k) - ((int) Math.pow(31, k)) * goal.charAt(index - 1);
  }

  private int computeHashCode(String str) {
    return str.hashCode();
  }
}

  private long pow(int x, int n) {
    if (n == 1) {
      return x;
    }
    if (n % 2 == 0) {
      return pow(x * x, n / 2);
    } else {
      return x * pow(x * x, (n - 1) / 2);
    }
  }

x = a + b;
if ((x^a) < 0 && (x^b) < 0)
{
    //overflow, do something
}

  /**
   * 求两个数的最大公约数
   * @param m
   * @param n
   * @return
   */
  private int gcd(int m, int n) {
    if (m == n) {
      return m;
    }
    if (m < n) {
      m ^= n;
      n ^= m;
      m ^= n;
    }
    if (isEven(m) && isEven(n)) {
      return 2 * gcd(m >> 1, n >> 1);
    } else if (isEven(m) && isOdd(n)) {
      return gcd(m >> 1, n);
    } else if (isOdd(m) && isEven(n)) {
      return gcd(m, n >> 1);
    } else {
      return gcd((m + n) >> 1, (m - n) >> 1);
    }
  }

  private boolean isEven(int m) {
    return m % 2 == 0;
  }

  private boolean isOdd(int m) {
    return m % 2 == 1;
  }

  /**
   * 求两个数的最大公约数
   * @param m
   * @param n
   * @return
   */
  private int gcd(int m, int n) {
    if (m < n) {
      m = m ^ n;
      n = n ^ m;
      m = m ^ n;
    }
    int r = 0;
    while ((r = m % n) != 0) {
      m = n;
      n = r;
    }
    return n;
  }

  /**
   * 查找数组中下标与元素值相同的元素的索引，没找到则返回-1
   * @param arr 需要查找的数组
   * @return 查找到的数组的索引
   */
  private int find(int[] arr) {
    int i = 0, j = arr.length - 1;
    while (i <= j) {
      int mid = (i + j) / 2;
      if (arr[mid] == mid) {
        return mid;
      }
      if (arr[mid] > mid) {
        j = mid - 1;
      } else {
        i = mid + 1;
      }
    }
    return -1;
  }

  /**
   * 计算函数式f(x) = a[n]x^n + a[n-1]x^(n-1) + a[n-2]x^(n-2) + ...+ a[0]算法，
   * 这里params数组中保存的是函数式的参数，顺序为从左到右，函数最高幂次为params.length - 1
   * @param params 参数数组
   * @param x 计算的变量
   * @return 计算结果
   */
  private double compute(double[] params, double x) {
    double poly = 0;
    for (int i = 0; i < params.length; i++) {
      poly = x * poly + params[i];
    }
    return poly;
  }