Pagini recente » Cod sursa (job #234295) | Cod sursa (job #1453946) | Istoria paginii runda/simulare_oni_hlo_mediu/clasament | Cod sursa (job #2016661) | Cod sursa (job #880749)
Cod sursa(job #880749)
#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;
}