KMP pattern matching

#1

my code is not returning anything.
#include<bits/stdc++.h>
using namespace std;
#define Max_N 10005
int reset[Max_N];
void kmppreprocess(string pat)
{
int i;
while( i<pat.size())
{
int i=0,j=-1;
reset[0]=-1;
while(j>=0&&pat[i]!=pat[j])
{
j=reset[j];
}
i++;j++;
reset[i]=j;
}
}
void kmp(string str,string pat)
{
kmppreprocess(pat);
int i=0,j=0;
while( i<str.size())
{
while(j>=0 && str[i]!=pat[j])
{
j=reset[j];

    }
    i++;
    j++;
    reset[i]=j;
}
if(j==pat.size())
{
    cout<<"pattern found at:"<<i-j<<endl;
    j=reset[j];
}

}
int main()
{
string str=“abaabcxabcxabxa”;
string pat=“abcxabx”;
for(int i=0;i<Max_N;i++)
{
reset[i]=-1;
}
kmp(str,pat);
return 0;
}

#2

This code is not returning anything on my system.

#3

Hi
Please Share link of code on ide.codingblocks.com

#4

#include
#include
using namespace std;
#define Max_N 100
int reset[Max_N];
void kmppreprocess(string pat)
{
int i;
while( i<pat.size())
{
int i=0,j=-1;
reset[0]=-1;
while(j>=0&&pat[i]!=pat[j])
{
j=reset[j];
}
i++;j++;
reset[i]=j;
}
}
void kmp(string str,string pat)
{
kmppreprocess(pat);
int i=0,j=0;
while( i<str.size())
{
while(j>=0 && str[i]!=pat[j])
{
j=reset[j];

    }
    i++;
    j++;
    reset[i]=j;
}
if(j==pat.size())
{
    cout<<"pattern found at:"<<i-j<<endl;
    j=reset[j];
}

}
int main()
{
string str;
string pat;
for(int i=0;i<Max_N;i++)
{
reset[i]=-1;
}
cin>>str;
cin>>pat;

kmp(str,pat);
return 0;

}

#5

Hi the reason why your code is not returning anything is because:
in the kmppreprocess function you have the following code:
int i;
while( i<pat.size())
{
int i=0,j=-1;
reset[0]=-1;
…
}
the i in the condition of the loop is never updated, so the condition is always true. The i you are updating is a local variable inside the while loop and not the i in the condition of the while loop.

This is the reason why the code is stuck.

#6

It seems there are other mistakes as well in the code, try fixing this one first.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.