686. 重复叠加字符串匹配

我的版本

  1. class Solution {
  2.     public int repeatedStringMatch(String a, String b) {
  3.         int aId = 0, bId = 0, aLen = a.length(), bLen = b.length(), bool = 0, rs = 0, abegin = 0;
  4.         if (bLen == 0) return rs;
  5.         while (bId < bLen) {
  7.             if (aId == aLen && bool == 1) {  // a重叠一次
  8.                 aId = 0;
  9.                 rs ++;
  10.             }
  12.             if (aId == aLen && bool == 0) break;   // a不满足条件
  14.             if (a.charAt(aId) == b.charAt(bId)) {
  15.                 if (bool != 1) {  
  16.                     bool = 1;
  17.                     rs = 1;
  18.                     abegin = aId;
  19.                 }
  20.                 bId ++;
  21.             } else if (bool == 1) {
  22.                 bId = 0;
  23.                 aId = abegin;
  24.                 rs = 0;
  25.                 bool = 0;
  26.             }
  28.             aId ++;
  29.         }
  30.         if (rs == 0) rs = -1;
  31.         return rs;
  32.     }
  33. }

KMP

在尝试使用KMP求解时，发现一个很有趣的点：

  1. "abaabaa"
  2. "abaababaab"

如上例子，可以发现如果使用next数组判断的时候，会陷入死循环，不断地：

0 0 a a
1 1 b b
2 2 a a
3 3 a a
4 4 b b
5 5 a a
6 6 a b
6 3 a a
0 4 a b
------------
0 0 a a
1 1 b b
2 2 a a
3 3 a a
4 4 b b
5 5 a a
6 6 a b
6 3 a a
0 4 a b
------------
0 0 a a
1 1 b b
2 2 a a
3 3 a a
4 4 b b
5 5 a a
6 6 a b
6 3 a a
0 4 a b
------------
……

代码：

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int aId = 0, bId = 0, aLen = a.length(), bLen = b.length(), bool = 0, rs = 0, abegin = 0;
        if (bLen == 0) return rs;
        int[] next = getNext(b);
        while (bId < bLen) {

            if (aId == aLen && bool == 0) break;   // a不满足条件
            if (aId == aLen && bool == 1) {  // a重叠一次
                aId = 0;
                rs ++;
            }

            if (a.charAt(aId) == b.charAt(bId)) {
                if (bool != 1) {  
                    bool = 1;
                    rs = 1;
                }
                bId ++;
                aId ++;
            } else {
                bId = next[bId];
                bool = 0;
                rs = 0;
                if (bId == -1) {
                    bId = 0;
                    aId ++;
                }
            } else {

            }
        }
        if (rs == 0) rs = -1;
        return rs;
    }
    public int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }
}

参考答案的KMP

在应用 Knuth-Morris-Pratt 算法时，被匹配字符串是循环叠加的字符串，所以下标要进行取余操作，并且匹配终止的条件为 b 开始匹配的位置超过第一个叠加的 a.

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int an = a.length(), bn = b.length();
        int index = strStr(a, b);
        if (index == -1) {
            return -1;
        }
        if (an - index >= bn) {
            return 1;
        }
        return (bn + index - an - 1) / an + 2;
    }

    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i - j < n; i++) { // b 开始匹配的位置是否超过第一个叠加的 a
            while (j > 0 && haystack.charAt(i % n) != needle.charAt(j)) { // haystack 是循环叠加的字符串，所以取 i % n
                j = pi[j - 1];
            }
            if (haystack.charAt(i % n) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}