Repeated String Match
Given two strings A and B, find the minimum number of times A has to be repeated such that B becomes a substring of the repeated A. If B cannot be a substring of A no matter how many times it is repeated, return -1.
Time : O(n + m)
Space : O(min(n, m))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { vector<int > PI (string& s) { int n = s.length (); vector<int > pi (n) ; for (int i = 1 , j = 0 ; i < n; i++) { while (j > 0 and s[i] != s[j]) j = pi[j - 1 ]; if (s[i] == s[j]) pi[i] = ++j; } return pi; } int kmp (string s, string& t) { int n = s.length (), m = t.length (); vector<int > pi = PI (t); for (int i = 0 , j = 0 ; i < n; i++) { while (j > 0 and s[i] != t[j]) j = pi[j - 1 ]; if (s[i] == t[j]) { if (++j == m) { return i; } } } return -1 ; } public : int repeatedStringMatch (string A, string B) { int n = A.length (), m = B.length (); if (n == m) return A == B ? 1 : -1 ; if (n > m) return kmp (A, B) != -1 ? 1 : kmp (A + A, B) != -1 ? 2 : -1 ; int pos = kmp (B, A); if (pos == -1 ) return -1 ; int left = pos - n; if (left >= n) return -1 ; int res = 1 + (left >= 0 ); for (int i = n - 1 ; i >= 0 and left >= 0 ; i--, left--) { if (A[i] != B[left]) return -1 ; } for (int i = pos + 1 , j = 0 ; i < m; i++) { if (j == 0 ) res++; if (A[j] != B[i]) return -1 ; j = (j + 1 ) % n; } return res; } };