Given two strings A and B. Find minimum number of times A has to be repeated such that B is a Substring of it. If B can never be a substring then return -1.
return pi; } intkmp(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 > 0and s[i] != t[j]) j = pi[j - 1]; if(s[i] == t[j]) { if(++j == m) return i; } }
return-1; } public: intminRepeats(string A, string B){ string s = ""; int res = 0; while(s.length() < B.length()) { s += A; res++; } returnkmp(s, B) != -1 ? res : kmp(s + A, B) != -1 ? res + 1 : -1; } };