SRM401 Div2 Hard

1000

お手上げ。解説を読む。

KMP の接頭語関数の最後の要素と文字長の差を見るらしい
接頭辞関数って、最長の接頭辞の長さだよね・・・。


スパソから KMP を拝借してサブミット

vector<int> buildFail(const char *p)
{
  int m = strlen(p);
  vector<int> fail(m + 1);
  int j = fail[0] = -1;
  for (int i = 1; i <= m; ++i) {
    while (j >= 0 && p[j] != p[i-1]) j = fail[j];
    fail[i] = ++j;
  }
  return fail;
}

class RunningLetters {
public:
  int newsLength(vector <string> R)
  {
    istringstream iss(accumulate(R.begin(), R.end(), string("")));
    string s;
    for (string t, u; iss >> t >> u; ) {
      int n = atoi(t.c_str());
      while (n--) s += u;
    }

    vector<int> v = buildFail(s.c_str());
    return s.size() - v.back();
  }
};