[AtCoder] 第二回全国統一プログラミング王決定戦本戦 B – NIKKEI String

2019年12月21日2020年12月18日

問題

方針

\( n = |S| \) とします。\( S_3 , \ S_4 \) を固定して考えます。\( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) \( (0 \leq i \leq j \leq n – 1)\)とします。このとき、

\begin{eqnarray}
S_3 &=& S(i, j)\\
S_4 &=& S(i + j + 1, i + 2j + 1)
\end{eqnarray}

と表現できます。また、制約は、\( 1 \leq i \leq n – 4 \wedge 0 \leq i + 2j +1\leq n – 3 \) です。次に、\( S_2, \ S_6 \) について探索を行います。これは、\( S_2, \ S_6 \) の末尾から先頭に向かって走査していくことで実現可能です。尺取り法のように文字列を伸ばしていく感じだと思います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string S;
    cin >> S;
    int n = S.length();
    
    int ans = 0;
    for (int i = 2; i < n - 3; i++) {
        for (int j = 0; i + 2 * j + 1 <= n - 3; j++) {
            // s3(i, i+j), s4(i+j+1, i+2j+1)
            string s3 = S.substr(i, j + 1);
            string s4 = S.substr(i + j + 1, j + 1);
            if (s3 != s4) continue;
            for (int k = 0; k < n; k++) {
                if (i - 1 - k <= 0) break;
                if (n - k - 1 <= i + 2 * j + 2) break;
                if (S[i - 1 - k] != S[n - k - 1]) break;
                ans++;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}