May 2015 – Live with passion

10067

Asif NaeemMay 26, 2015

#include <iostream>
#include <queue>

using namespace std;

bool visit[10][10][10][10];

int arr[3]={0,1,-1};

struct states{
	int a,b,c,d;
	int step;
	};

int main()
{
	int t,n,stp;
	states tmp;
	int tw,tx,ty,tz;
	int a,b,c,d,x,y,w,z;
	cin>>t;
	while(t--)
	{
		states src,trgt,tmp;

		for(int i=0;i<10;i++)
			for(int j=0;j<10;j++)
				for(int k=0;k<10;k++)
					for(int l=0;l<10;l++)
						visit[i][j][k][l]=0;
		cin>>a>>b>>c>>d;
		src.a=a; src.b=b;
		src.c=c; src.d=d;
		src.step=0;

		cin>>a>>b>>c>>d;
		trgt.a=a; trgt.b=b;
		trgt.c=c; trgt.d=d;
		trgt.step=-1;

		cin>>n;

		for(int i=0;i<n;i++)
		{
			cin>>a>>b>>c>>d;
			visit[a][b][c][d]=1;
		}

		queue<states> q;
		q.push(src);
		while(!q.empty())
		{
			tmp = q.front();q.pop();
			w=tmp.a;
			x=tmp.b;
			y=tmp.c;
			z=tmp.d;
			stp=tmp.step;
			visit[w][x][y][z]=1;

			if(w==trgt.a && x==trgt.b && y==trgt.c && z==trgt.d)
			{
				trgt.step=stp;
				break;
			}

			int tarr[4]={w,x,y,z};
			for(int i=0;i<4;i++)
			{
				int xx=tarr[i];
				tarr[i]=(tarr[i]+1)%10;
				if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)
				{
					tmp.a=tarr[0]; tmp.b=tarr[1];
					tmp.c=tarr[2]; tmp.d=tarr[3];
					tmp.step=stp+1;
					visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;
					q.push(tmp);
				}
				tarr[i]=xx;
				tarr[i]=((xx-1)<0?9:(xx-1)%10);
				if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)
				{
					tmp.a=tarr[0]; tmp.b=tarr[1];
					tmp.c=tarr[2]; tmp.d=tarr[3];
					tmp.step=stp+1;
					visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;
					q.push(tmp);
				}
				tarr[i]=xx;
			}
			//cout<<"sdjj\n";
		}
		if(trgt.step!=-1)
		cout<<trgt.step<<"\n";
		else
		cout<<-1<<"\n";
	}

	return 0;
}

100

101

#include <iostream>

#include <queue>

using namespace std;

bool visit[10][10][10][10];

int arr[3]={0,1,-1};

struct states{

int a,b,c,d;

int step;

};

int main()

{

int t,n,stp;

states tmp;

int tw,tx,ty,tz;

int a,b,c,d,x,y,w,z;

cin>>t;

while(t--)

{

states src,trgt,tmp;

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

for(int j=0;j<10;j++)

for(int k=0;k<10;k++)

for(int l=0;l<10;l++)

visit[i][j][k][l]=0;

cin>>a>>b>>c>>d;

src.a=a; src.b=b;

src.c=c; src.d=d;

src.step=0;

cin>>a>>b>>c>>d;

trgt.a=a; trgt.b=b;

trgt.c=c; trgt.d=d;

trgt.step=-1;

cin>>n;

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

{

cin>>a>>b>>c>>d;

visit[a][b][c][d]=1;

}

queue<states> q;

q.push(src);

while(!q.empty())

{

tmp = q.front();q.pop();

w=tmp.a;

x=tmp.b;

y=tmp.c;

z=tmp.d;

stp=tmp.step;

visit[w][x][y][z]=1;

if(w==trgt.a && x==trgt.b && y==trgt.c && z==trgt.d)

{

trgt.step=stp;

break;

}

int tarr[4]={w,x,y,z};

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

{

int xx=tarr[i];

tarr[i]=(tarr[i]+1)%10;

if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)

{

tmp.a=tarr[0]; tmp.b=tarr[1];

tmp.c=tarr[2]; tmp.d=tarr[3];

tmp.step=stp+1;

visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;

q.push(tmp);

}

tarr[i]=xx;

tarr[i]=((xx-1)<0?9:(xx-1)%10);

if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)

{

tmp.a=tarr[0]; tmp.b=tarr[1];

tmp.c=tarr[2]; tmp.d=tarr[3];

tmp.step=stp+1;

visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;

q.push(tmp);

}

tarr[i]=xx;

}

//cout<<"sdjj\n";

}

if(trgt.step!=-1)

cout<<trgt.step<<"\n";

else

cout<<-1<<"\n";

}

return 0;

}

10047

Asif NaeemMay 25, 2015

#include <iostream>
#include <queue>

#define Green 0
#define Black 1
#define Red 2
#define Blue 3
#define White 4

#define N 0
#define W 1
#define S 2
#define E 3

using namespace std;

struct states{
	int ro,col,wt,direction,wheelcolr;
	};

int m,n,ans;


bool bfs(states src,states trgt,char gr[30][30])
{
	int r,c,d,colr,weight;
	states tmp;
	queue<states> q;
	q.push(src);
	bool visit[30][30][4][5];//r,c,dir,col
	for(int i=0;i<30;i++)
		for(int j=0;j<30;j++)
			for(int k=0;k<4;k++)
				for(int l=0;l<5;l++)
					visit[i][j][k][l]=0;

	while(!q.empty())
	{
		tmp=q.front();q.pop();
		r=tmp.ro; c=tmp.col; d=tmp.direction; colr=tmp.wheelcolr;
		weight=tmp.wt;
		visit[r][c][d][colr]=true;

		if(r==trgt.ro && c==trgt.col && colr==Green)
		{
			trgt.wt=weight;
			ans=weight;
			return 1;
		}
		if(d==N)
		{
			if(!visit[r][c][E][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][W][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(r-1>=0 && !visit[r-1][c][N][(colr+1)%5] && gr[r-1][c]!='#')
			{
				tmp.ro=r-1; tmp.col=c; tmp.direction=N; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==S)
		{
			if(!visit[r][c][E][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][W][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(r+1<m && !visit[r+1][c][S][(colr+1)%5] && gr[r+1][c]!='#')
			{
				tmp.ro=r+1; tmp.col=c; tmp.direction=S; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==W)
		{
			if(!visit[r][c][N][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][S][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(c-1>=0 && !visit[r][c-1][W][(colr+1)%5] && gr[r][c-1]!='#')
			{
				tmp.ro=r; tmp.col=c-1; tmp.direction=W; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==E)
		{
			if(!visit[r][c][N][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][S][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(c+1<n && !visit[r][c+1][E][(colr+1)%5] && gr[r][c+1]!='#')
			{
				tmp.ro=r; tmp.col=c+1; tmp.direction=E; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}

	}
	return 0;
}
int main()
{
	int kase=1;
	while(cin>>m)
	{
		cin>>n;
		if(m+n==0)
		break;
		states src,trgt;
		char gr[30][30];
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>gr[i][j];
				if(gr[i][j]=='S')
				{
					src.ro=i;src.col=j;src.wt=0;
					src.direction=N;src.wheelcolr=Green;
				}
				if(gr[i][j]=='T')
				{
					trgt.ro=i;trgt.col=j;trgt.wt=0;
					trgt.direction=0;trgt.wheelcolr=Green;
				}
			}
		}

		if(kase>1)
			cout<<"\nCase #"<<kase++<<"\n";
		else
			cout<<"Case #"<<kase++<<"\n";
		if(!bfs(src,trgt,gr))
		{
			cout<<"destination not reachable\n";
		}
		else
		{
			cout<<"minimum time = "<<ans<<" sec\n";
		}
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

#include <iostream>

#include <queue>

#define Green 0

#define Black 1

#define Red 2

#define Blue 3

#define White 4

#define N 0

#define W 1

#define S 2

#define E 3

using namespace std;

struct states{

int ro,col,wt,direction,wheelcolr;

};

int m,n,ans;

bool bfs(states src,states trgt,char gr[30][30])

{

int r,c,d,colr,weight;

states tmp;

queue<states> q;

q.push(src);

bool visit[30][30][4][5];//r,c,dir,col

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

for(int j=0;j<30;j++)

for(int k=0;k<4;k++)

for(int l=0;l<5;l++)

visit[i][j][k][l]=0;

while(!q.empty())

{

tmp=q.front();q.pop();

r=tmp.ro; c=tmp.col; d=tmp.direction; colr=tmp.wheelcolr;

weight=tmp.wt;

visit[r][c][d][colr]=true;

if(r==trgt.ro && c==trgt.col && colr==Green)

{

trgt.wt=weight;

ans=weight;

return 1;

}

if(d==N)

{

if(!visit[r][c][E][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][W][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(r-1>=0 && !visit[r-1][c][N][(colr+1)%5] && gr[r-1][c]!='#')

{

tmp.ro=r-1; tmp.col=c; tmp.direction=N; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

else if(d==S)

{

if(!visit[r][c][E][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][W][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(r+1<m && !visit[r+1][c][S][(colr+1)%5] && gr[r+1][c]!='#')

{

tmp.ro=r+1; tmp.col=c; tmp.direction=S; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

else if(d==W)

{

if(!visit[r][c][N][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][S][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(c-1>=0 && !visit[r][c-1][W][(colr+1)%5] && gr[r][c-1]!='#')

{

tmp.ro=r; tmp.col=c-1; tmp.direction=W; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

else if(d==E)

{

if(!visit[r][c][N][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][S][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(c+1<n && !visit[r][c+1][E][(colr+1)%5] && gr[r][c+1]!='#')

{

tmp.ro=r; tmp.col=c+1; tmp.direction=E; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

return 0;

}

int main()

{

int kase=1;

while(cin>>m)

{

cin>>n;

if(m+n==0)

break;

states src,trgt;

char gr[30][30];

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

{

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

{

cin>>gr[i][j];

if(gr[i][j]=='S')

{

src.ro=i;src.col=j;src.wt=0;

src.direction=N;src.wheelcolr=Green;

}

if(gr[i][j]=='T')

{

trgt.ro=i;trgt.col=j;trgt.wt=0;

trgt.direction=0;trgt.wheelcolr=Green;

}

if(kase>1)

cout<<"\nCase #"<<kase++<<"\n";

else

cout<<"Case #"<<kase++<<"\n";

if(!bfs(src,trgt,gr))

{

cout<<"destination not reachable\n";

}

else

{

cout<<"minimum time = "<<ans<<" sec\n";

}

return 0;

}

1645

Asif NaeemMay 16, 2015

#include <iostream>
#include <cstdio>

#define ll long long

using namespace std;
ll dp[1010];

int main()
{
	int n,kase=1;

	dp[1]=1;

	for(int i=2;i<1001;i++)
	{
		for(int j=1;j<i;j++)
		{
			if((i-1)%j==0)
			{
				dp[i]+=dp[j];
				dp[i]%=1000000007;
			}
		}
	}

	while(scanf("%d",&n)!=EOF)
	{
		cout<<"Case "<<kase++<<": "<<dp[n]<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#define ll long long

using namespace std;

ll dp[1010];

int main()

{

int n,kase=1;

dp[1]=1;

for(int i=2;i<1001;i++)

{

for(int j=1;j<i;j++)

{

if((i-1)%j==0)

{

dp[i]+=dp[j];

dp[i]%=1000000007;

}

while(scanf("%d",&n)!=EOF)

{

cout<<"Case "<<kase++<<": "<<dp[n]<<"\n";

}

return 0;

}

11340

Asif NaeemMay 13, 2015

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

using namespace std;
map<char,int> mp;

int main()
{
	int t,n,k,val;
	char c;

	cin>>t;
	getchar();
	while(t--)
	{
		cin>>n;
		getchar();
		mp.clear();
		while(n--)
		{
			scanf("%c %d",&c,&val);
			getchar();
			mp[c]=val;
		}
		cin>>k;
		getchar();
		double ans=0;
		while(k)
		{
			c=getchar();
			if(c=='\n')
			k--;
			else
			ans+=mp[c];
		}
		printf("%.2lf$\n",ans/100);
	}

	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <map>

using namespace std;

map<char,int> mp;

int main()

{

int t,n,k,val;

char c;

cin>>t;

getchar();

while(t--)

{

cin>>n;

getchar();

mp.clear();

while(n--)

{

scanf("%c %d",&c,&val);

getchar();

mp[c]=val;

}

cin>>k;

getchar();

double ans=0;

while(k)

{

c=getchar();

if(c=='\n')

k--;

else

ans+=mp[c];

}

printf("%.2lf$\n",ans/100);

}

return 0;

}

Probability: Probability of survival without spin = (total number of adjacent pair of zeros)/(total number of empty + bullets ); Probability of survival with spin/rotation = (total number of zeros)/(total number of empty + bullets ); SO, P_s_without_spin = total adjacent zero/length; P_s_with_spin = total zero/length; if(P_s_without_spin == P_s_with_spin) total adjacent zero/length = P_s_with_spin =

Continue Reading “1636” →

1644

Asif NaeemMay 2, 2015

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

int n;
int arr[1300000];
vector<int> v;

int main()
{
	int lo,hi,mid;
	for(int i=0;i<1300000;i++)
	{
		arr[i]=0;
	}

	for(int i=2;i<sqrt(1300000);i++)
	{
		if(arr[i]==0)
		{
			for(int j=i+i;j<1300000;j+=i)
			{
				arr[j]=1;
			}
		}
	}

	for(int i=2;i<1300000;i++)
	{
		if(arr[i]==0)
		{
			v.push_back(i);
		}
	}
	//cout<<v.size()<<"\n";
	while(scanf("%d",&n),n)
	{
		if(arr[n]==0)
		{
			cout<<0<<"\n";
			continue;
		}
		lo=0;hi=v.size()-1;
		while(hi-lo>1)
		{
			if((hi-lo)%2)
			{
				mid=lo+(hi-lo)/2+1;
			}
			else
				mid=lo+(hi-lo)/2;
			//cout<<lo<<" "<<mid<<" "<<hi<<" "<<n<<"\n";
			//getchar();
			if(n<v[mid])
			{
				hi=mid;
			}
			else
			{
				lo=mid;
			}
		}
		cout<<v[hi]-v[lo]<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

int n;

int arr[1300000];

vector<int> v;

int main()

{

int lo,hi,mid;

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

{

arr[i]=0;

}

for(int i=2;i<sqrt(1300000);i++)

{

if(arr[i]==0)

{

for(int j=i+i;j<1300000;j+=i)

{

arr[j]=1;

}

for(int i=2;i<1300000;i++)

{

if(arr[i]==0)

{

v.push_back(i);

}

//cout<<v.size()<<"\n";

while(scanf("%d",&n),n)

{

if(arr[n]==0)

{

cout<<0<<"\n";

continue;

}

lo=0;hi=v.size()-1;

while(hi-lo>1)

{

if((hi-lo)%2)

{

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

}

else

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

//cout<<lo<<" "<<mid<<" "<<hi<<" "<<n<<"\n";

//getchar();

if(n<v[mid])

{

hi=mid;

}

else

{

lo=mid;

}

cout<<v[hi]-v[lo]<<"\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;

}

Pattern Search Problem

Asif NaeemMay 2, 2015

There are several algorithm to solve pattern search from a provided string problem. To solve such problem using Naive method(for all the char of the provided string check whether the pattern contains or not ). It takes O(m*n),here m = string length of pattern and n= string length of the text. There are several algorithm to solve

Continue Reading “Pattern Search Problem” →

Month: May 2015

10067

10047

1645

11340

1636

1644

10679

Pattern Search Problem

Archives

Categories