KMP Algorithm – Live with passion

10298

Asif NaeemDecember 31, 2015

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

int lps[1000005];

void prefixArray(string s)
{
	memset(lps,0,sizeof(lps));
	int len=0;//length of prev longest prefix
	int i=1;
	lps[0]=0;
	int length = s.size();
	while(i<length)
	{
		if(s[i]==s[len])
		{
			len+=1;
			lps[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len = lps[len-1];
			}
			else
			{
				lps[i]=0;
				i+=1;
			}
		}
	}
}
int main()
{
	string s;
	int lastval,minimal_length_of_repeated_string;
	while(cin>>s)
	{
		if(s==".")
		break;
		prefixArray(s);
		lastval = lps[s.size()-1];
		minimal_length_of_repeated_string = s.size()-lastval;
		if(s.size()%minimal_length_of_repeated_string==0)
		printf("%d\n",s.size()/minimal_length_of_repeated_string);
		else
		printf("1\n");
	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdio>

#include <string>

using namespace std;

int lps[1000005];

void prefixArray(string s)

{

memset(lps,0,sizeof(lps));

int len=0;//length of prev longest prefix

int i=1;

lps[0]=0;

int length = s.size();

while(i<length)

{

if(s[i]==s[len])

{

len+=1;

lps[i]=len;

i+=1;

}

else

{

if(len!=0)

{

len = lps[len-1];

}

else

{

lps[i]=0;

i+=1;

}

int main()

{

string s;

int lastval,minimal_length_of_repeated_string;

while(cin>>s)

{

if(s==".")

break;

prefixArray(s);

lastval = lps[s.size()-1];

minimal_length_of_repeated_string = s.size()-lastval;

if(s.size()%minimal_length_of_repeated_string==0)

printf("%d\n",s.size()/minimal_length_of_repeated_string);

else

printf("1\n");

}

return 0;

}

Theory: The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3)

Continue Reading “1282” →

11475

Asif NaeemAugust 11, 2015

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdlib>

#define INF 1000000
#define ll long long

using namespace std;

int main()
{
	char s[100005];
	string str;
	int len,i,j,idx;
	int *failureFunc;

	while(scanf("%s",s)!=EOF)
	{
		len=strlen(s);
		str="";
		for(int y=len-1;y>=0;y--)
		str.append(1u,s[y]);

		failureFunc=(int *)malloc(sizeof(int)*len);

		failureFunc[0]=0;
		i=0;
		j=1;
		while(j<len)
		{
			if(str[i]==str[j])
			{
				i+=1;
				failureFunc[j]=i;
				j+=1;
			}
			else
			{
				if(i)
				{
					i=failureFunc[i-1];
				}
				else
				{
					failureFunc[j]=0;
					j+=1;
				}
			}
		}

		//match s and str(asume as pattern)
		i=0;j=0;
		int mx_idx=-1;
		while(i<len)
		{
			if(s[i]==str[j])
			{
				i+=1;j+=1;
				mx_idx=j;
			}
			else
			{
				if(j)
				j=failureFunc[j-1];
				else
				i+=1;
			}
		}

		string res="";
		for(int y=j;y<str.size();y++)
		res.append(1u,str[y]);

		printf("%s",s);
		cout<<res<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <cstdlib>

#define INF 1000000

#define ll long long

using namespace std;

int main()

{

char s[100005];

string str;

int len,i,j,idx;

int *failureFunc;

while(scanf("%s",s)!=EOF)

{

len=strlen(s);

str="";

for(int y=len-1;y>=0;y--)

str.append(1u,s[y]);

failureFunc=(int *)malloc(sizeof(int)*len);

failureFunc[0]=0;

i=0;

j=1;

while(j<len)

{

if(str[i]==str[j])

{

i+=1;

failureFunc[j]=i;

j+=1;

}

else

{

if(i)

{

i=failureFunc[i-1];

}

else

{

failureFunc[j]=0;

j+=1;

}

//match s and str(asume as pattern)

i=0;j=0;

int mx_idx=-1;

while(i<len)

{

if(s[i]==str[j])

{

i+=1;j+=1;

mx_idx=j;

}

else

{

if(j)

j=failureFunc[j-1];

else

i+=1;

}

string res="";

for(int y=j;y<str.size();y++)

res.append(1u,str[y]);

printf("%s",s);

cout<<res<<"\n";

}

return 0;

}

10679

Asif NaeemMay 2, 2015

KMP algo solution*
*/
/*
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <iostream>

using namespace std;
void computeLPSArray(char *pat, int M, int *lps);

bool KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    // create lps[] that will hold the longest prefix suffix values for pattern
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    while (i < N)
    {
      if (pat[j] == txt[i])
      {
        j++;
        i++;
      }

      if (j == M)
      {
        //printf("Found pattern at index %d \n", i-j);
        return 1;
        j = lps[j-1];
      }

      // mismatch after j matches
      else if (i < N && pat[j] != txt[i])
      {
        // Do not match lps[0..lps[j-1]] characters,
        // they will match anyway
        if (j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
    free(lps); // to avoid memory leak
    return 0;
}

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // lenght of the previous longest prefix suffix
    int i;

    lps[0] = 0; // lps[0] is always 0
    i = 1;

    // the loop calculates lps[i] for i = 1 to M-1
    while (i < M)
    {
       if (pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if (len != 0)
         {
           // This is tricky. Consider the example AAACAAAA and i = 7.
           len = lps[len-1];

           // Also, note that we do not increment i here
         }
         else // if (len == 0)
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}

// Driver program to test above function
int main()
{
	int t,q;
	char txt[1000005];
   char pat[1010];
	cin>>t;
	getchar();
	while(t--)
	{
		gets(txt);
		cin>>q;
		getchar();
		while(q--)
		{
			gets(pat);
			bool f = KMPSearch(pat, txt);
			if(f)
			cout<<"y\n";
			else
			cout<<"n\n";
		}
	}

   return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

KMP algo solution*

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include <iostream>

using namespace std;

void computeLPSArray(char *pat, int M, int *lps);

bool KMPSearch(char *pat, char *txt)

{

int M = strlen(pat);

int N = strlen(txt);

// create lps[] that will hold the longest prefix suffix values for pattern

int *lps = (int *)malloc(sizeof(int)*M);

int j = 0; // index for pat[]

// Preprocess the pattern (calculate lps[] array)

computeLPSArray(pat, M, lps);

int i = 0; // index for txt[]

while (i < N)

{

if (pat[j] == txt[i])

{

j++;

i++;

}

if (j == M)

{

//printf("Found pattern at index %d \n", i-j);

return 1;

j = lps[j-1];

}

// mismatch after j matches

else if (i < N && pat[j] != txt[i])

{

// Do not match lps[0..lps[j-1]] characters,

// they will match anyway

if (j != 0)

j = lps[j-1];

else

i = i+1;

}

free(lps); // to avoid memory leak

return 0;

}

void computeLPSArray(char *pat, int M, int *lps)

{

int len = 0; // lenght of the previous longest prefix suffix

int i;

lps[0] = 0; // lps[0] is always 0

i = 1;

// the loop calculates lps[i] for i = 1 to M-1

while (i < M)

{

if (pat[i] == pat[len])

{

len++;

lps[i] = len;

i++;

}

else // (pat[i] != pat[len])

{

if (len != 0)

{

// This is tricky. Consider the example AAACAAAA and i = 7.

len = lps[len-1];

// Also, note that we do not increment i here

}

else // if (len == 0)

{

lps[i] = 0;

i++;

}

// Driver program to test above function

int main()

{

int t,q;

char txt[1000005];

char pat[1010];

cin>>t;

getchar();

while(t--)

{

gets(txt);

cin>>q;

getchar();

while(q--)

{

gets(pat);

bool f = KMPSearch(pat, txt);

if(f)

cout<<"y\n";

else

cout<<"n\n";

}

return 0;

}

This problem also can be solved using Suffix array but gets TLE. Code as follows:

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

struct suffix{
	int idx;
	char *suffixArr;
};
int arr[1000001];
int res[100005];
int qry[1005];

int cmp(suffix a,suffix b)
{
	return (strcmp(a.suffixArr,b.suffixArr)<0?1:0);
}
void buildSuffixArray(char *str)
{
	int n=strlen(str);
	suffix SUFX[n];

	for(int i=0;i<n;i++)
	{
		SUFX[i].idx=i;
		SUFX[i].suffixArr=(str+i);
	}

	sort(SUFX,SUFX+n,cmp);

	//int *arr=new int[n];

	for(int i=0;i<n;i++)
	{
		arr[i]=SUFX[i].idx;
	}
	//return arr;
}

bool search(char *patern,char *str,int *arr)
{
	int len=strlen(str);
	int m=strlen(patern);

	int lo=0,hi=len-1,mid;
	while(lo<=hi)
	{
		mid=lo+(hi-lo)/2;
		//int strncmp(const char *s1, const char *s2, size_t n);
		int r = strncmp(patern,str+arr[mid],m);
		if(r==0)
		{
			return 1;
		}
		else if(r<0)
		{
			hi=mid-1;
		}
		else if(r>0)
		{
			lo=mid+1;
		}
	}
	return 0;
}

int main()
{
	int t,q;
	char strres[1000000];
	char strqry[10000];
	cin>>t;
	getchar();
	while(t--)
	{
		gets(strres);
		for(int i=0;i<strlen(strres);i++)
		{
			if(strres[i]>='A' && strres[i]<='Z')
				res[i]=strres[i]-'A';
			else
				res[i]=strres[i]-'a'+26;
		}
		cin>>q;
		getchar();
		buildSuffixArray(strres);
		while(q--)
		{
			gets(strqry);
			for(int i=0;i<strlen(strqry);i++)
			{
				if(strqry[i]>='A' && strqry[i]<='Z')
				qry[i]=strqry[i]-'A';
				else
				qry[i]=strqry[i]-'a'+26;
			}
			bool f = search(strqry,strres,arr);
			if(f)
			cout<<"y\n";
			else
			cout<<"n\n";
		}
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <iostream>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

struct suffix{

int idx;

char *suffixArr;

};

int arr[1000001];

int res[100005];

int qry[1005];

int cmp(suffix a,suffix b)

{

return (strcmp(a.suffixArr,b.suffixArr)<0?1:0);

}

void buildSuffixArray(char *str)

{

int n=strlen(str);

suffix SUFX[n];

for(int i=0;i<n;i++)

{

SUFX[i].idx=i;

SUFX[i].suffixArr=(str+i);

}

sort(SUFX,SUFX+n,cmp);

//int *arr=new int[n];

for(int i=0;i<n;i++)

{

arr[i]=SUFX[i].idx;

}

//return arr;

}

bool search(char *patern,char *str,int *arr)

{

int len=strlen(str);

int m=strlen(patern);

int lo=0,hi=len-1,mid;

while(lo<=hi)

{

mid=lo+(hi-lo)/2;

//int strncmp(const char *s1, const char *s2, size_t n);

int r = strncmp(patern,str+arr[mid],m);

if(r==0)

{

return 1;

}

else if(r<0)

{

hi=mid-1;

}

else if(r>0)

{

lo=mid+1;

}

return 0;

}

int main()

{

int t,q;

char strres[1000000];

char strqry[10000];

cin>>t;

getchar();

while(t--)

{

gets(strres);

for(int i=0;i<strlen(strres);i++)

{

if(strres[i]>='A' && strres[i]<='Z')

res[i]=strres[i]-'A';

else

res[i]=strres[i]-'a'+26;

}

cin>>q;

getchar();

buildSuffixArray(strres);

while(q--)

{

gets(strqry);

for(int i=0;i<strlen(strqry);i++)

{

if(strqry[i]>='A' && strqry[i]<='Z')

qry[i]=strqry[i]-'A';

else

qry[i]=strqry[i]-'a'+26;

}

bool f = search(strqry,strres,arr);

if(f)

cout<<"y\n";

else

cout<<"n\n";

}

return 0;

}

Category: KMP Algorithm

10298

1282

11475

10679

Archives

Categories