Grupe X - 6.6.10 / pag 178

#include <bits/stdc++.h>

using namespace std;

const int di[] = {-1, 0, 1, 0, -1, -1, 1, 1},
          dj[] = {0, 1, 0, -1, -1, 1, -1, 1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector < string > a(N + 1);
    for(int i = 1; i <= N; ++i) {
        cin >> a[i];
        a[i] = '$' + a[i];
    }
    string s;
    cin >> s;
    s = '$' + s;
    int k = s.size() - 1;
    vector < vector < int > > dp(N + 1, vector < int >(M + 1));
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if(a[i][j] == s[1])
                dp[i][j] = 1;
    /* dp[i][j] = nr. de ap. al subsirului din s care incepe la poz. 1 si se termina
    pe poz. coresp. elementului a[i][j] */
    auto inside = [&](int lin, int col) {
        return lin > 0 && col > 0 && lin <= N && col <= M;
    };
    for(int l = 2; l <= k; ++l)
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= M; ++j)
                if(a[i][j] == s[l])
                    for(int d = 0; d < 8; ++d) {
                        int lin = i + di[d],
                            col = j + dj[d];
                        if(inside(lin, col) && a[lin][col] == s[l - 1])
                            dp[i][j] += dp[lin][col];
                    }
    int ans = 0;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if(a[i][j] == s[k])
                ans += dp[i][j];
    cout << ans;
}