33 lines
600 B
C++
33 lines
600 B
C++
#include "s0459_repeated_substring_pattern.hpp"
|
|
|
|
void S0459::getNext(string &s, int *next) {
|
|
int j{0};
|
|
int len = s.size();
|
|
next[0] = 0;
|
|
for (int i{1}; i < len; ++i) {
|
|
while (j > 0 && s[i] != s[j]) {
|
|
j = next[j - 1];
|
|
}
|
|
if (s[i] == s[j]) {
|
|
++j;
|
|
}
|
|
next[i] = j;
|
|
}
|
|
}
|
|
|
|
bool S0459::repeatedSubstringPattern(string s) {
|
|
int len = s.size();
|
|
if (len <= 1) {
|
|
return false;
|
|
}
|
|
int next[len];
|
|
getNext(s, next);
|
|
if (next[len - 1] == 0) {
|
|
return false;
|
|
} else if (len % (len - next[len - 1]) == 0) {
|
|
return true;
|
|
} else {
|
|
return false;
|
|
}
|
|
}
|