变形词问题

比较两个字符串中包含的字符是否完全一样，不考虑顺序

暴力法

将字符串A中的每个字符与字符串B中的每个字符进行比较，如果相同则将字符串B中的该字符置为0，表示已经比较过了，如果不同则返回false，如果字符串B中的所有字符都比较完了，那么返回true

排序法

将字符串A和字符串B都排序，然后比较排序后的字符串是否相等

字符统计法

如果是ASCII码，可以使用长度为256的数组,统计字符串A中每个字符出现的次数,然后遍历字符串B，每遍历到一个字符，就将对应的统计数组的值减一，如果出现负数，说明字符串B中的字符出现的次数比字符串A中的多，返回false，如果遍历完字符串B，统计数组中没有负数，说明字符串A和字符串B中的字符完全一样，返回true

如果是Unicode码，可以使用长度为65536的数组或HashMap。

旋转词

将字符串前面任意部分挪到后面形成的字符串，称为旋转词。有A、B两个字符串，判断B是否是A的旋转词所包含的子串。

将A再拼接一个A，则A的旋转形式都能在型字符串中找到对应的子串。这时再判断B是否是A+A的子串即可。

字符串匹配

求字符串A中是否包含字符串B

暴力匹配

boolean matchDirect(String strA, String strB) {
  if (strA == null || strB == null) {
   return false;
  }
  char[] charsA = strA.toCharArray();
  char[] charsB = strB.toCharArray();
  for (int i = 0; i <= charsA.length - charsB.length; i++) {
   int temp = 0;
   while (temp < charsB.length && charsA[i + temp] == charsB[temp]) {
    temp++;
   }
   if (temp==charsB.length){
    return true;
   }
  }
  return false;
}

RabinKarp

对字符串中每字符串B个长度的字串进行hash计算，这样直接和字符串B的哈希进行比较就可以判断是否包含 hash = (((C0 *31+c1)*31)+...+Cn-1 * 31)+Cn 计算子串hash可以使用滚动哈希，每次加上尾部的减去头部的 不用重复计算中间的。 为防止字符串B比较长，计算出的hash值超过了Long.Max范围，可以将计算出的hash对Long.MAX取余数 当然为了防止哈希碰撞，当hash相等时还是要检验一下字符串是否真的相等。

KMP算法

暴力匹配法 每次失配的时候,字符串B要回退到头部，字符串A也要回退相应的长度-1，然后重新开始匹配

如果字符串B中有相同的前缀和后缀，那么其实不用每次都从头开始匹配，只需回退到这个前缀的下一位开始匹配即可

比如字符串B是 adbadcd 当匹配到第6个字符c的时候失配，但是c之前的子串adbad 有相同的前缀和后缀ad,那么可以想到字符串B回退到头部，字符串A也相应回退5位开始匹配，这样的效果其实和字符串A不动，字符串B回退到第三位开始匹配效果是一样的，也就是回退到下标等于前缀长度的位置。

所以解题的关键是对字符串B的每一位字符，求得该位之前的子串的最大相同前后缀，这样，在之后的匹配中就可以很快定位到失配后应该重新开始的地方，这便是KMP的算法思想。

计算字符串B每个位置的最大相同前后缀的思路： 使用数组next[B.length]保存每一位失配后，对应的重新匹配的位置 next[0] = -1 next[1] = 0 对于i>1 next[i] 有next[i-1] = k 说明i-1位最大相同前后缀长度为k, 那么比较一下B[k]和B[i-1] 是否相同， 如果相同，说明next[i] =k+1, 如果不同，说明这个前后缀长了，再短一点看看有没有相同前后缀，则看next(k) 因为第k位之前的前后缀也必然出现在第i-1位之前的前后缀中，只不过没有第i-1为之前的最大前后缀长，这个是可以传递的。 next[k] = t ,比较B[t]与B[i-1]是否相同，相同则next(i) = t+1,不相同则k=t,重复上面的步骤，直到next[k]=-1,这时next[i] = 0

以字符串B=bababcd为例 i=0 b 往前没有字符 next[0] = -1 i=1 ba 往前只有一个字符 nex[1] = 0 i=2 bab 往前字符串 ba 观察上一位k = next[i-1]=next[1=0 则比较B[0]与B[i-1],不相同，看next[0] = -1 ,则next[2] = 0 i=3 baba k=next[2] = 0 ,B[2]==B[0] ,next[3] = k+1 =1; i=4 babab k = next[3] = 1,B[3]==B[1] ,next[4] = 1+1=2; i=5 bababc k = next[4]=2, B[4]==B[2] next[5] =3 i=6 bababcd k = next[5] = 3,B[5]!=B[3] ,k=next[3]=1,B[5]!=B[1],k=next[1]=0 ,B[5]!=B[0] ,k=next[0]=-1,next[6]=0

后缀数组法

思路：构造字符串A的所有的后缀子串，如果后缀子串是以字符串B开头的，那么可知字符串A包含字符串B 但是在与字符串B比较的时候，还是要将后缀子串和字符串B的每一位进行比较 为了减少这一操作，可以对后缀子串进行排序，排序之后就可以使用二分查找，快速定位到开头是以B字符串开头的子串。 所以关键是对后缀子串的排序。如果逐位比较，复杂度n^2。 优化思路：倍增法 先只根据第一位字符排序，使用快排 再排前两位，但是在排序的时候因为第一位已经有了排名，如果排名相同，再排第二位， 但是第二位其实在第一次排序的时候也已经有了排名。 再排前四位 前两位已有排名，如果排名相同，再比后两位，后两位在上一次排序中也已经有了排名。 所以需要维护一个排名的数组，下标是子串开头的字符串在原字符串的下标位置，值是排名。 时间复杂度 外部倍增次数为logN次，内部快排每次NlogN次 O(N(logN)^2)

 //辅助类 用来记录后缀子串的起始下标 和起始字符
 class Suff {
  public int index;
  public char sufferChar;

  public Suff(int index, char sufferChar) {
   this.index = index;
   this.sufferChar = sufferChar;
  }
 }
 private boolean matchSuffer(String strA, String strB) {
  if (strA == null || strA.length() == 0 || strB == null ||strB.length() == 0){
   return false;
  }
  //得到排序的后缀子串数组
  Suff[] suffs = getSuffsSorted(strA);
  int l = 0,r = strA.length() -1;
  char[] chars = strA.toCharArray();
  //二分查找
  while (l<=r){
   int mid = l + ((r-l)>>1);
   Suff midSuff = suffs[mid];
   int i = compare(chars,midSuff.index,strB);
   if (i == 0){
    return true;
   }else if (i<0){
    l = mid+1;
   }else {
    r = mid -1;
   }
  }
  return false;
 }
 //比较后缀数组与匹配字符的大小关系 需要注意只用到后缀子串的前部分，根据匹配字符串的长度而定，而后缀子串可能没有那么长
 private int compare(char[] chars,int beginIndex,String strB){
  int i = 0;
  while (i<chars.length && i<strB.length() ){
   if ( chars[i+beginIndex] == strB.charAt(i)){
    i++;
   }else {
    return chars[i+beginIndex] - strB.charAt(i);
   }
  }
  if (i == strB.length()){
   return 0;
  }
  return -1;
 }
 //得到排好序的后缀数组
 private Suff[] getSuffsSorted(String strA) {
  int[] rk = new int[strA.length()];
  Suff[] suffs = new Suff[strA.length()];
  for (int j = 0; j < strA.length(); j++) {
   suffs[j] = new Suff(j, strA.charAt(j));
  }
  Arrays.sort(suffs, Comparator.comparingInt(e -> e.sufferChar));
  int length = 1;
  sortRank(suffs,rk,strA,length);
  do {
   length *= 2;
   final int i = length;
   Arrays.sort(suffs, (e1, e2) -> {
    if (rk[e1.index] == rk[e2.index]) {
     if (strA.length() > e1.index + i / 2 && strA.length() > e2.index + i / 2) {
      return rk[e1.index + i / 2] - rk[e2.index + i / 2];
     } else {
      return -(e1.index - e2.index);
     }
    } else {
     return rk[e1.index] - rk[e2.index];
    }
   });
   sortRank(suffs,rk,strA,length);
  } while (length <= strA.length());
  return suffs;
 }
 //维护排名数组
 private void sortRank(Suff[] suffs,int[] rk,String strA,int length){
  int r = 0;
  rk[suffs[0].index] = r;
  for (int j = 1; j < suffs.length; j++) {
   if (isSameWithPrev(suffs,j,length,strA)){
    rk[suffs[j].index] = r;
   }else {
    rk[suffs[j].index] = ++r;
   }
  }
 }
 //辅助维护排名数组 比较是否与上一个排名相同
 private boolean isSameWithPrev(Suff[] suffs, int j, int length, String strA) {
  Suff prev = suffs[j-1];
  Suff cur = suffs[j];
  if (cur.sufferChar != prev.sufferChar){
   return false;
  }
  int i = 0;
  while (i<length && i+cur.index<strA.length()  && i+prev.index<strA.length()){
   if (strA.charAt(cur.index+i) != strA.charAt(prev.index+i)){
    return false;
   }
   i++;
  }
  return i == length;
 }

引申： 求所有后缀子串， 公共前缀的最大长度 同样的 可以对后缀子串进行排序，然后遍历后缀数组，计算第i个和i+1个后缀子串的公共前缀的长度，找出最大值。 优化点：对于字符串abcabc 他的子串排序后有 abc abcabc bc bcabc c cabc 当我们计算abc abcabc 后，再计算bc bcabc的时候可以发现，它们只是前面的一对去掉了帽子a，如果前面公共前缀长度为k，那么后者的公共前缀长度必然大于等于k-1(去掉了一个帽子a),因此我们只需要从第k位开始比较即可。 所以我们需要维护一个自然序的后缀子串数组，和一个排序后的后缀子串数组，遍历自然序数组，找出对应的后缀子串在排序数组中的位置，从上一次的到的k-1位开始计数比较即可。