**1. Brute Force (Naive Approach)**\nNot much efficient : But Logic is important which is used further while Rabin-Karp implementation of this problem. \n\n**Time complexity :** **`O(N.M)`**\n**Space complexity :** **`O(M)`** *(temporary string)*\n**`Time : 1799ms (It takes hell lot of time)`**\n![image](https://assets.leetcode.com/users/images/a74b2958-9ea5-4c9c-aa35-f752d62a4ab8_1658220262.6419485.png)\n\n```\nclass Solution {\npublic:\n \n bool check(string &a, string &b)\n {\n int m=a.size();\n int n=b.size();\n \n for(int i=0;i<=m-n;i++)\n {\n int j;\n for(j=0;j text string \n // s2 -> pattern string\n // Check pattern find in text or not !!\n // Rolling hash : hash calculation in sliding window, window moves by 1 step in right \n int Rabin_Karp(string s1, string s2) \n {\n long long m=s1.size();\n long long n=s2.size();\n \n long long p = 31;\n long long pow = 1;\n long long mod = 1e9+7;\n long long targetHashVal = 0;\n \n // targetHashVal - calculate hash value of pattern\n for(long long i=0;ipha(m);\n // power array : so that my time is not wasting in calculating big powers\n vectorpa(m);\n \n pha[0] = s1[0]-\'a\'+1;\n pa[0] = 1;\n pow = p;\n \n for(long long i=1;i0)\n win = (win - pha[sp-1]+mod)%mod; // agar value negative hoti hai toh usme bas mod add kardo\n \n if(win == (targetHashVal*pa[sp])%mod){\n return 1;\n }\n sp++,ep++;\n }\n return 0;\n }\n \n int repeatedStringMatch(string A, string B) \n {\n // edge cases\n if(A == B) return 1;\n \n int count = 1;\n string source = A;\n while(source.size() < B.size()){\n source+=A;\n count++;\n }\n \n // edge cases\n if(source == B) \n return count;\n \n if(Rabin_Karp(source,B) == 1) \n return count;\n \n if(Rabin_Karp(source+A,B) == 1) \n return count+1;\n return -1;\n }\n};\n```\n\n----\n**Note :**\nThe average and best-case running time of the **Rabin-Karp algorithm** is **`O(N+M)`**, \nbut its worst-case time is **`O(N*M)`**. \nWorst case of Rabin-Karp algorithm occurs when all characters of pattern and text are same as the hash values of all the substrings of **`txt[]`** match with hash value of **`pat[]`**. For example **`pat[] = \u201CAAA\u201D`** and **`txt[] = \u201CAAAAAAA\u201D`**.\n\n----\n\n**3. KMP Algo for Substring search**\n\n**Time complexity :** **`O(M+N)`** \n**Space complexity :** **`O(N)`** *(prefix LPS array)*\n**`Time : 4ms`**\n```\nclass Solution {\npublic: \n \n // s --> text\n // p --> pattern\n int KMP_search(string s, string p)\n {\n int m=s.size();\n int n=p.size();\n \n // longest proper prefix : longest "prefix" is same as "suffix" \n vectorlps(n,0);\n int len=0, i=1;\n \n // Dry run for pattern = "abcabcd", then you will understand clearly how we will create "LPS" array\n // pattern ----------> a b c a b c d\n // "lps" array comes --> 0 0 0 1 2 3 0\n while(i

Repeated String Match

Problem Description

Problem Description

Answer Panel