Cod sursa(job #1376375)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 5 martie 2015 17:13:20
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<fstream>
#include<string>

using namespace std;

ifstream fin( "matrix.in" );
ofstream fout( "matrix.out" );

const int nmax = 1000;
const int nrlit = 26;
int f[ nrlit + 1 ];
int w[ nmax + 1 ][ nmax + 1 ];
int s[ nmax + 1 ][ nmax + 1 ];
string g[ nmax + 1 ];

inline int cate( int i, int j, int lat ) {
    return s[ i ][ j ] - s[ i - lat ][ j ] - s[ i ][ j - lat ] + s[ i - lat ][ j - lat ];
}
int main() {
    int n, m;
    string x;
    fin >> n >> m;
    for( int i = 1; i <= n; ++ i ) {
        fin >> g[ i ]; g[ i ] = "#" + g[ i ];
    }
    for( int i = 1; i <= m; ++ i ) {
        fin >> x;
        for( int j = 0; j < m; ++ j ) {
            ++ f[ x[ j ] - 'a' ];
        }
    }
    for( int k = 0; k < nrlit; ++ k ) {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                s[ i ][ j ] = s[i - 1][ j ] + s[ i ][j - 1] - s[i - 1][j - 1] + (g[ i ][ j ] - 'a' == k);
            }
        }
        for( int i = m; i <= n; ++ i ) {
            for( int j = m; j <= n; ++ j ) {
                if ( f[ k ] == cate( i, j, m ) ) {
                    ++ w[ i ][ j ];
                }
            }
        }

    }
    int ans = 0;
    for( int i = m; i <= n; ++ i ) {
        for( int j = m; j <= n; ++ j ) {
            ans += (w[ i ][ j ] == nrlit);
        }
    }
    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}