Created
July 19, 2022 12:08
-
-
Save icameling/f641e824242221c18a68b8afaabf469f to your computer and use it in GitHub Desktop.
#字符串 #重复的子字符串
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
void get_pmt(const string& s, int*pmt) { | |
pmt[0] = 0; | |
int j = 0; | |
for (int i = 1; i < s.size(); ++i) { | |
while (j > 0 && s[i] != s[j]) | |
j = pmt[j - 1]; | |
if (s[i] == s[j]) | |
j++; | |
pmt[i] = j; | |
} | |
} | |
bool repeatedSubstringPattern(string s) { | |
if (s.size() <= 1) | |
return false; | |
int pmt[s.size()]; | |
get_pmt(s, pmt); | |
// aabc aabc aabc | |
// 0100 1234 5678 | |
// abc abcabcabc" | |
// 000 123456789 | |
// aaaaaaaa | |
// 01234567 | |
// abab | |
// 0012 | |
// abac | |
// 0010 | |
int k = s.size() - pmt[s.size() - 1]; | |
if (pmt[s.size() - 1] > 0 && s.size() % k == 0) | |
return true; | |
else | |
return false; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment