Pagini recente » Cod sursa (job #2275488) | Cod sursa (job #2370940) | Cod sursa (job #627540) | iTzBirion | Cod sursa (job #2362236)
#include <fstream>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
const int VAL=1005;
const int CAR=35;
int MOD[3], NR[3];
int N, M, i, j, ANS;
int PUT[3][65], cnt;
int dp[3][VAL][VAL];
int lin[3][VAL][VAL];
int col[3][VAL][VAL];
string S[VAL], T[VAL];
int main()
{
fin >> M >> N;
MOD[1]=30103;
MOD[2]=37891;
PUT[1][0]=PUT[2][0]=1;
for (i=1; i<CAR; i++)
{
for (j=1; j<=2; j++)
{
PUT[j][i]=PUT[j][i-1]*26;
PUT[j][i]%=MOD[j];
}
}
for (i=1; i<=M; i++)
{
fin >> T[i];
T[i]='*'+T[i];
}
for (i=1; i<=N; i++)
{
fin >> S[i];
S[i]='*'+S[i];
for (j=1; j<=N; j++)
{
for (cnt=1; cnt<=2; cnt++)
{
NR[cnt]+=PUT[cnt][T[i][j]-'a'];
if (NR[cnt]>=MOD[cnt])
NR[cnt]-=MOD[cnt];
}
}
}
for (i=1; i<=M; i++)
{
for (j=1; j<=M; j++)
{
for (cnt=1; cnt<=2; cnt++)
{
lin[cnt][i][j]=lin[cnt][i][j-1]+PUT[cnt][S[i][j]-'a'];
if (j>N)
lin[cnt][i][j]-=PUT[cnt][S[i][j-N]-'a'];
lin[cnt][i][j]%=MOD[cnt];
if (lin[cnt][i][j]<0)
lin[cnt][i][j]+=MOD[cnt];
col[cnt][i][j]=col[cnt][i-1][j]+PUT[cnt][S[i][j]-'a'];
if (i>N)
col[cnt][i][j]-=PUT[cnt][S[i-N][j]-'a'];
if (col[cnt][i][j]<0)
col[cnt][i][j]+=MOD[cnt];
}
}
}
for (i=1; i<=N; i++)
{
for (cnt=1; cnt<=2; cnt++)
{
dp[cnt][N][N]+=lin[cnt][i][N];
if (dp[cnt][N][N]>=MOD[cnt])
dp[cnt][N][N]-=MOD[cnt];
}
}
if (dp[1][N][N]==NR[1] && dp[2][N][N]==NR[2])
ANS++;
for (i=N; i<=M; i++)
{
for (j=N; j<=M; j++)
{
if (i==N && j==N)
continue;
for (cnt=1; cnt<=2; cnt++)
{
if (j==N)
dp[cnt][i][j]=dp[cnt][i-1][j]+lin[cnt][i][j]-lin[cnt][i-N][j];
else
dp[cnt][i][j]=dp[cnt][i][j-1]+col[cnt][i][j]-col[cnt][i][j-N];
dp[cnt][i][j]%=MOD[cnt];
if (dp[cnt][i][j]<0)
dp[cnt][i][j]+=MOD[cnt];
}
if (dp[1][N][N]==NR[1] && dp[2][N][N]==NR[2])
ANS++;
}
}
fout << ANS << '\n';
fin.close();
fout.close();
return 0;
}