Given two strings S1 and S2, form a R*C
matrix with the string S1 (You may repeat the string S1 to fill in the rest of
the matrix, if length of S1 is less than R*C). Then search for the string S2
along rows from left to right or along columns from top to bottom) and print
the number of occurrence of S2.
Input
Format:
The first line contains R and C separated
by a space. The second line contains S1. The third line contains S2.
Output
Format:
The first line contains the integer value
denoting the number of occurrence of S2 in the character matrix formed.
Boundary
Conditions:
2 <= R, C <= 100
2 <= Length of S1 <= 10000
2 <= Length of S2 <= 200
Example Input/Output 1:
Input:
5 4
managermetuatten
man
Output:
3
Explanation:
The 5*4 character matrix formed using S1 is mana germ etua tten mana man can be found in 1st row from left to right and in 4th column from top to bottom. Then it is also found in 5th row. Hence the overall occurrence count is 2.
The 5*4 character matrix formed using S1 is mana germ etua tten mana man can be found in 1st row from left to right and in 4th column from top to bottom. Then it is also found in 5th row. Hence the overall occurrence count is 2.
Solution:
#include <iostream>
using namespace std;
int main()
{
int n,m,i,j,f,c=0;
string s,t;
cin>>n>>m>>s>>t;
int k=0,l=s.size(),p=t.size();
char a[n][m];
for(i=0;i<n;i++)
for(j=0;j<m;j++,k=k%l)
a[i][j]=s[k++];
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(j+p-1<m)
{
f=0;
for(k=0;k<p;k++)
if(a[i][j+k]!=t[k])
f=1;
if(f==0)
c++;
}
if(i+p-1<n)
{
f=0;
for(k=0;k<p;k++)
if(a[i+k][j]!=t[k])
f=1;
if(f==0)
c++;
}
}
cout<<c;
}