Cod sursa(job #880749)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 17 februarie 2013 11:33:56
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <fstream>
#include <iostream>
#include <iterator>
#include <bitset>
#include <algorithm>

#define MAX_SIZE 1001

#define CHARVAL(ch) ((ch) - 'a')

using namespace std;

static char line[MAX_SIZE];
static char humanGenome[MAX_SIZE][MAX_SIZE];
static int geneSearch[MAX_SIZE][MAX_SIZE];
static bitset<MAX_SIZE> mismatches[MAX_SIZE];

static int alienGenomeMap[32];

int main()
{
    int n,m;
    fstream fin("matrix.in", fstream::in);
    fstream fout("matrix.out", fstream::out);
    
    fin >> m >> n;
    //cout << m << " " << n << endl;
    
    for (int i=0; i<m; ++i)
    {
        fin >> humanGenome[i];
    }
    
    for (int i=0; i<n; ++i)
    {
        fin >> line;
        for (int j=0; j<n; ++j)
        {
            ++alienGenomeMap[CHARVAL(line[j])];
        }
    }
    
    for (int letter=0; letter < 26; ++letter)
    {
        for (int i=1; i<=m; ++i)
        {
            for (int j=1; j<=m; ++j)
            {
                geneSearch[i][j] = geneSearch[i-1][j] + geneSearch[i][j-1] - geneSearch[i-1][j-1] + (letter == CHARVAL(humanGenome[i-1][j-1]));
                //cout << geneSearch[i][j] << " ";
            }
            //cout << endl;
        }
        //cout << endl << endl;
        
        for (int i=n; i<=m; ++i)
        {
            for (int j=n; j<=m; ++j)
            {
                if (!mismatches[i][j])
                {
                    const int numLetter = geneSearch[i][j] - geneSearch[i-n][j] - geneSearch[i][j-n] + geneSearch[i-n][j-n];
                    //cout << numLetter << " ";
                    
                    mismatches[i][j] = (numLetter != alienGenomeMap[letter]);
                    //cout << endl << "heh " << numLetter << " " << alienGenomeMap[letter] << endl;
                }
            }
            //cout << endl;
        }
        //cout << endl << endl;
    }
    
    int matches = 0;
    for (int i=n; i<=m; ++i)
    {
        matches += (m - mismatches[i].count() - n + 1);
        //cout << mismatches[i].to_string() << endl;
    }
    
    fout << matches << "\n";
    
    return 0;
}