CareerCup

use KMP matching
in each column and each row

Complexity will be O( (m+n)*(m+n))

where matrix is m * m
and n=length of input string

anyone knows the answer to this one?

@ gautam
yes this i also think about to use kmp here
and complexity will be theta(m*m)
in KMP there are two main steps
FIRST STEP is to make and prefix array PIE
and using this do the searching of pattern in matcher step in step 2
PREFIX FUNCTION
void Prefix(char P[],int m,int PRE[])
{
int q,k=0;
PRE[1]=0;
for(q=2;q<=m;q++)
{
while(k>0 && PRE[k+1]!=PRE[q])
k=PRE[k];
if(P[k+1]=P[q])
k++;
PRE[q]=k;
}}

for matching
void MATCHER(char T[],int n,char P[],int m)
{
in q,k,i,j;
int PRE[100];
Prefix(P,m,PRE);
q=0;
for(i=1;i<=n;i++)
{
while(q>0 && P[q+1]!=T[i])
q=PRE[q];
if(P[q+1]==T[i])
q++;
if(q==m)
{
printf("the string found at%d",i-m);
q=PRE[q];// for the next match
}


}

}