Submission #294369

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,n) for(__typeof((n).begin()) it=(n).begin();it!=(n).end();++it)

using namespace std;

long long rhash[255][255];
long long rrhash[255][255];

long long bpow[255];

vector<string> field;

long long base = 1000000009;

long long getrhash(int i, int j, int k) {
    return rhash[i][k] - rhash[i][j] * bpow[k - j];
}

long long getrrhash(int i, int j, int k) {
    return rrhash[i][j] - rrhash[i][k] * bpow[k - j];
}

int main() {
    int r, c;
    cin >> r >> c;
    field = vector<string>(r);
    rep(i, r) {
        cin >> field[i];
    }

    bpow[0] = 1;
    rep(i, c) {
        bpow[i + 1] = bpow[i] * base;
    }

    rep(i, r) {
        rep(j, c) {
            rhash[i][j + 1] = rhash[i][j] * base + field[i][j];
        }

        for (int j = c; j > 0; j--) {
            rrhash[i][j - 1] = rrhash[i][j] * base + field[i][j - 1];
        }
    }

    int ans = 0;

    for (int d = 2; d <= c; d++) {
        for (int j = 0; j + d <= c; j++) {
            for (int i = 0; i < r; i++) { // center
                if (getrhash(i, j, j + d) != getrrhash(i, j, j + d)) continue;
                for (int h = 1; i - h >= 0 && i + h < r; h++) {
                    if (getrhash(i - h, j, j + d) == getrrhash(i + h, j, j + d)) ans++;
                    else break;
                }
            }

            for (int i = 0; i - 1 < r; i++) {
                for (int h = 1; i - h + 1 >= 0 && i + h < r; h++) {
                    if (getrhash(i - h + 1, j, j + d) == getrrhash(i + h, j, j + d)) ans++;
                    else break;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result