Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Gift and Chef CodeChef Solution
Problem -Gift and Chef CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
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() {
// your code goes here
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) {
// your code goes here
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;
import java.io.InputStreamReader;
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 {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
while (T-- > 0) {
String text = reader.readLine();
String pattern = reader.readLine();
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])%1000000007Gift 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.
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!
