anim
BAN USERKMP
int kmp()
{
int i;
kmptable();
int k=-1;
for(i=0;i<m;i++)
{
while(k>-1&&pattern[k+1]!=text[i])
{
k=table[k];
}
if(text[i]==pattern[k+1])
{
k++;
}
if(k==n-1)
{
return i-k+1;
}
}
return -1;
}
void kmptable()
{
int k=-1;
int i=1;
table[0]=k;
for(i=1;i<n;i++)
{
while(k>-1&&pattern[k+1]!=pattern[i])
{
k=table[k];
}
if(pattern[i]==pattern[k+1])
{
k++;
}
table[i]=k;
}
}
One more solution in cpp :-)
#include <iostream>
using namespace std;
enum State{RIGHT,DOWN,LEFT,UP};
State goRight(int arr[][5],int &col,int &row,int &colStart, int &colEnd, int &rowStart, int &rowEnd)
{
//if(col<=colEnd&&col>=colStart)
col++;
cout<<arr[row][col];
if(col == colEnd)
{
rowStart++;
return DOWN;
}
return RIGHT;
}
State goDown(int arr[][5],int &col,int &row,int &colStart, int &colEnd, int &rowStart, int &rowEnd)
{
//if(row<=rowEnd&&row>=rowStart)
row++;
cout<<arr[row][col];
if(row == rowEnd)
{
colEnd--;
return LEFT;
}
return DOWN;
}
State goLeft(int arr[][5],int &col,int &row,int &colStart, int &colEnd, int &rowStart, int &rowEnd)
{
//if(col<=colEnd&&col>=colStart)
col--;
cout<<arr[row][col];
if(col == colStart)
{
rowEnd--;
return UP;
}
return LEFT;
}
State goUP(int arr[][5],int &col,int &row,int &colStart, int &colEnd, int &rowStart, int &rowEnd)
{
//if(row<=rowEnd&&row>=rowStart)
row--;
cout<<arr[row][col];
if(row == rowStart)
{
colStart++;
return RIGHT;
}
return UP;
}
void printArr(int arr[][5],int cols,int rows)
{
State state = RIGHT;
int colStart=0,colEnd=cols-1;
int rowStart=0,rowEnd=rows-1;
int col=0,row=0;
cout << arr[row][col];
while(colStart<=colEnd&&rowStart<=rowEnd)
{
switch(state)
{
case RIGHT:
state=goRight(arr,col,row,colStart,colEnd,rowStart,rowEnd);
break;
case DOWN:
state=goDown(arr,col,row,colStart,colEnd,rowStart,rowEnd);
break;
case LEFT:
state=goLeft(arr,col,row,colStart,colEnd,rowStart,rowEnd);
break;
case UP:
state=goUP(arr,col,row,colStart,colEnd,rowStart,rowEnd);
break;
}
}
}
Didnot compile this, it takes the first mentioned approach
- anim April 03, 2014