给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

    注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。

    示例 1：

    输入：a = “abcd”, b = “cdabcdab”
    输出：3
    解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。
    示例 2：

    输入：a = “a”, b = “aa”
    输出：2
    示例 3：

    输入：a = “a”, b = “a”
    输出：1
    示例 4：

    输入：a = “abc”, b = “wxyz”
    输出：-1

    提示：

    1 <= a.length <= 104
    1 <= b.length <= 104
    a 和 b 由小写英文字母组成

    1. class Solution {
    2.     /**
    3.     字符串匹配首先想到kmp算法，但我们需要先保证能匹配成功的条件：
    4.     1.b中不存在a中没有的字母
    5.     2.a的长度要大于等于b(还得处理刚好相等时，再加一次复制的情况)
    6.      */
    7.     int[] ne = new int[10010];
    8.     public int repeatedStringMatch(String a, String b) {
    9.         int n = a.length(), m = b.length();
    10.         int[] cnt1 = new int[26], cnt2 = new int[26];
    11.         for (int i = 0; i < n; ++i) cnt1[a.charAt(i)-'a']++;
    12.         for (int i = 0; i < m; ++i) cnt2[b.charAt(i)-'a']++;
    13.         //如果b中存在a中没有的字母就肯定不能匹配成功
    14.         for (int i = 0; i < 26; ++i) 
    15.             if (cnt1[i] == 0 && cnt2[i] != 0) return -1;
    16.         int count = 1;          //初始肯定得复制1次
    17.         String s = a;           
    18.         int k = n;
    19.         while (n < m) {         //当s长度小于b长度就一直复制
    20.             s = s + a;          //复制s
    21.             n += k;             
    22.             count++;
    23.         }
    24.         boolean isTrue = matching(s,b);
    25.         if (isTrue) return count;
    26.         /**
    27.         为什么还要匹配一次？因为存在
    28.         "abcd"
    29.         "cdabcdab"这种样例 得再复制尝试一次
    30.          */
    31.         count++;
    32.         s = s + a;
    33.         if (matching(s,b)) return count;
    34.         return -1;
    35.     }
    36.     //kmp算法
    37.     public boolean matching(String s1, String s2) {
    38.         int n = s1.length(), m = s2.length();
    39.         s1 = " " + s1;
    40.         s2 = " " + s2;
    41.         //求next
    42.         for (int i = 2, j = 0; i <= m; ++i) {
    43.             while (j > 0 && s2.charAt(i) != s2.charAt(j+1)) j = ne[j];
    44.             if (s2.charAt(i) == s2.charAt(j+1)) j++;
    45.             ne[i] = j;
    46.         }
    47.         //匹配过程
    48.         for (int i = 1, j = 0; i <= n; ++i) {
    49.             while (j > 0 && s1.charAt(i) != s2.charAt(j+1)) j = ne[j];
    50.             if (s1.charAt(i) == s2.charAt(j+1)) j++;
    51.             if (j == m) return true;
    52.         }
    53.         return false;
    54.     }
    55. }