304 North Cardinal St.
Dorchester Center, MA 02124

# Gift and Chef CodeChef Solution

## Gift and Chef CodeChef Solution in C++14

``````#include <iostream>
#include<vector>
#include<string>
using namespace std;
#define vv vector<int>

void calc1(vv &lps,string f)
{
int len1=f.length();

int i=1;
int len=0;
while(i<len1)
{
if(f[i]==f[len])
{
len++;
lps[i]=len;
i++;
}
else
{
if(len!=0)
len=lps[len-1];
else
{
lps[i]=0;
i++;
}

}
}

return;

}

void  compare1(vv &lps,string f,string s,vv &A)
{

int len1=s.length();
int len2=f.length();
int i,j;

i=0;
j=0;

while(j<len1)
{
if(f[i]==s[j])
{
i++;
j++;
}
if(i>=len2)
{
A[j-1]=1;
i=lps[i-1];
}
else if(j<len1 && f[i]!=s[j])
{
if(i!=0)
i=lps[i-1];
else
j++;
}
}

return;

}
int main() {

int t;

cin>>t;
int gh=1000000007;
int ar[400000];
while(t--)
{
string s,f;
cin>>s>>f;

int len1=s.length();
int len2=f.length();

vv A(len1);

vv lps(len2);

calc1(lps,f);

compare1(lps,f,s,A);

int i,j;

for(i=0;i<=len1;i++)
ar[i]=0;

for(i=1;i<=len1;i++)
{
if(A[i-1]==1)
{
ar[i]=(ar[i-len2]+1)%gh;
}
ar[i]=(ar[i]+ar[i-1])%gh;
}

cout<<ar[len1]<<endl;

}
return 0;
}``````

## Gift and Chef CodeChef Solution in PYTH 3

``````M = 10**9+7

def lps_compute(s):
n = len(s)
lps = [0]*n
curr = 0
lps[0] = 0
i = 1
while i < n:
if s[i]== s[curr]:
curr += 1
lps[i] = curr
i += 1
else:
if curr != 0:
curr = lps[curr-1]
else:
lps[i] = 0
i += 1
return lps

def kmp(s1,s2):
n,m = len(s1),len(s2)
lps = lps_compute(s2)
ans = [0]*n
i,j = 0,0
while i < n:
if s1[i] == s2[j]:
i += 1
j += 1
else:
if j==0:
i+=1
else:
j = lps[j-1]
if j == m:
ans[i-1] = 1
j = lps[j-1]
return ans

for _ in range(int(input())):
s1 = input().strip()
s2 = input().strip()
n,m = len(s1),len(s2)
arr = kmp(s1,s2)
dp = [0]*n
if arr[0] == 1:
dp[0] = 1
for i in range(1,n):
if arr[i]==1:
if i==m-1:
dp[i] = 1
else:
dp[i] = (1 + dp[i-m])%M
dp[i] = (dp[i-1]+dp[i])%M
print(dp[-1])``````

## Gift and Chef CodeChef Solution in C

``````#include <stdio.h>
#include <string.h>
int mod=1e9+7;
char S[300001],F[300001];
int dp[300003],b[300001],flag[300001];
void kmpPreprocess(int m)
{
int i = 0, j = -1; b[0] = -1;
while (i < m)
{
while (j >= 0 && F[i] != F[j]) j = b[j];
i++; j++;
b[i] = j;
}
}
void kmpSearch(int m,int n)
{
int i = 0, j = 0;
while (i < n)
{
while (j >= 0 && S[i] != F[j]) j = b[j];
i++; j++;
if (j == m)
{
//printf("P is found at index %d in T\n", i - j);
flag[i-j]=1;
j = b[j];
}
}
}
int main(void) {
int T,i,j;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
for(j=0;j<=300000;j++)flag[j]=0;
scanf("%s %s",S,F);
int l=strlen(F);
kmpPreprocess(l);
int l2=strlen(S);
kmpSearch(l,l2);
for(j=0;j<l;j++)dp[j]=0;
for(j=l-1;S[j]!='\0';j++)
{
dp[j+1]=dp[j];
char str[l+1];
if(flag[j-l+1])
dp[j+1]=((long long)dp[j+1]+dp[j+1-l]+1)%mod;
}
printf("%d\n",dp[j]);
}
return 0;
}``````

## Gift and Chef CodeChef Solution in JAVA

``````import java.io.BufferedReader;
import java.io.IOException;

class Main {

private static final int MOD = 1000000007;

private static int[] findMatches(String text, String pattern) {
int[] A = new int[text.length()];
int[] temp = new int[pattern.length()];
int i = 1;
int j = 0;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(j)) {
temp[i] = j + 1;
i++;
j++;
} else {
if (j != 0) {
j = temp[j - 1];
} else {
temp[i] = 0;
j = 0;
i++;
}
}
}

i = j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
A[i - 1] = 1;
j = temp[j - 1];
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j != 0) {
j = temp[j - 1];
} else {
i++;
}
}

}
return A;

}

public static void main(String[] args) throws IOException {

while (T-- > 0) {
int[] A = findMatches(text, pattern);

int[] dp = new int[text.length() + 1];
for (int i = pattern.length() - 1; i < text.length(); i++) {
if (A[i] == 1) {
dp[i + 1] = 1;
if (i >= pattern.length()) {
dp[i + 1] = (dp[i+1] + dp[i + 1 - pattern.length()]) % MOD;
}
}
dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
}
System.out.println(dp[text.length()]);

}

}
}``````

## Gift and Chef CodeChef Solution in PYTH

``````def fun(pat, M, lps):
tmp = 0

lps[0] = 0

i = 1;
while (i < M):
if (pat[i] == pat[tmp]):
tmp += 1
lps[i] = tmp
i += 1
else:
if (tmp != 0):
tmp = lps[tmp-1];
else:
lps[i] = 0
i += 1

for t in range(input()):
a=raw_input().strip()
b=raw_input().strip()
n,m=len(a),len(b)
ps=0
arr=[0]*m
dp=[0]*n
fun(b,m,arr)
index=0
i,j=0,0
while i<n:
if a[i]==b[j]:
i+=1
j+=1
if j==m:
for x in range(index,i-j):
ps+=dp[x]
ps%=1000000007
index = i-j
dp[i-1]=1+ps
j=arr[j-1]
elif i<n and a[i]!=b[j] :
if j!=0:
j=arr[j-1]
else:
i+=1
print sum([i%1000000007 for i in dp])%1000000007``````
##### Gift and Chef CodeChef Solution Review:

In our experience, we suggest you solve this Gift and Chef CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Gift and Chef CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Gift and Chef CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!