Cod sursa(job #1253761)

Utilizator mgntMarius B mgnt Data 1 noiembrie 2014 19:24:28
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#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;
}