読者です 読者をやめる 読者になる 読者になる

SRM 541 Div2 Easy AkariDaisukiDiv2

問題

問題文が面白いのでまるまる掲載.あかりって何かのアニメの主人公?
Consider the following function: f(X) = Waai + X + Akari + X + Daisuki Here, X is a string and + denotes string concatenation. Waai, Akari and Daisuki are constant non-empty strings.

You are given a string S. Compute and return the number of different tuples (Waai,Akari,Daisuki,X) such that f(X) equals S.

解答

Xに当たるのは1文字だと勘違いして最初ハマった.
Xの文字数を設定して,分割位置をi, jで指定,S[i..i+l-1] == S[j..j+l-1]ならカウントする.

class AkariDaisukiDiv2
{
public:
  int countTuples(string S)
    {
      int n = S.size();
      int i, j, l;
      int res = 0;
      for(l = 1; l < n; l++){
      for(i = 1; i < n; i++){
        for(j = i+l+1; j < n-l; j++){
          if (S.substr(i, l) == S.substr(j, l)) res++;
        }
      }
      }
      return res;
    }
};