Pagini recente » Cod sursa (job #706556) | Cod sursa (job #2194270) | Cod sursa (job #1378816) | Cod sursa (job #34623) | Cod sursa (job #1253761)
#include <fstream>
#include <vector>
#include <string>
bool
demo
()
{ // 1. Read question.
::std::ifstream is("matrix.in");
::std::size_t M;
::std::size_t N;
::std::size_t i;
::std::string wi;
is >> M >> N;
::std::vector < ::std::string > A(M);
::std::vector < ::std::string > B(N);
for(i=0; M>i; ++i)
{ is >> wi;
wi.swap(A[i] );
}
for(i=0; N>i; ++i)
{ is >> wi;
wi.swap(B[i] );
}
::std::size_t const max_n = 1000;
unsigned F[26];
unsigned C[max_n][26];
unsigned S[26];
::std::size_t k;
::std::size_t x;
// 2. Compute answer, from question.
unsigned answer = 0;
// 2.x. Build frequencies.
for(x=0; 26>x; ++x)
{ F[x] = 0;
}
for(k=0; N>k; ++k)
{ ::std::string const & w = B[k];
for(i=0; N>i; ++i)
{ x = static_cast < ::std::size_t > (w[i] - 'a');
++F[x];
}
}
// 2.x. Start counting.
for(i=0; M>i; ++i)
{ for(x=0; 26>x; ++x)
{ C[i][x] = 0;
}
}
// 2.x. For each column, count.
for(k=1; N>k; ++k)
{ ::std::string const & w = A[k-1];
for(i=0; M>i; ++i)
{ x = static_cast < ::std::size_t > (w[i] - 'a');
++C[i][x];
}
}
for(k=N-1; M>k; ++k)
{ if(N<=k)
{ // 2.x. Substract row.
::std::string const & w = A[k-N];
for(i=0; M>i; ++i)
{ x = static_cast < ::std::size_t > (w[i] - 'a');
--C[i][x];
}
}
// 2.x Add row.
{ ::std::string const & w = A[k];
for(i=0; M>i; ++i)
{ x = static_cast < ::std::size_t > (w[i] - 'a');
++C[i][x];
}
}
// 2.x. Prepare movement.
for(x=0; 26>x; ++x)
{ S[x] = 0;
}
for(i=1; N>i; ++i)
{ for(x=0; 26>x; ++x)
{ S[x] += C[i-1][x];
}
}
// 2.x. Move the square.
for(i=N-1; M>i; ++i)
{ if(N<=i)
{ // 2.x. Substract column.
for(x=0; 26>x; ++x)
{ S[x] -= C[i-N][x];
}
}
// 2.x. Add column.
{ for(x=0; 26>x; ++x)
{ S[x] += C[i][x];
}
}
// 2.x. Compare.
for(x=0; 26>x; ++x)
{ if(F[x] != S[x])
{ break;
}
}
// 2.x. Update answer.
if(26 == x)
{ ++answer;
}
}
}
// 3. Write answer.
::std::ofstream os("matrix.out");
os << answer << '\n';
return true; // Success.
}
int
main
()
{ int status;
try
{ bool const ok = demo();
status = ( ok ? 0 : 1 );
}
catch ( ... )
{ status = 2;
}
return status;
}