#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;
  }
}