Can you wait till tomm? I’ll surely write in detail by tomm. 
1 Like
Yeah sure, TIA.
Really good questions this contest!
Are there any specific reasons for having a large value of A in the string hashing solution?? @cherry0697 @nagpaljatin141
We can create a count_arr of size 2 \cdot \mid txt \mid where count_arr[i] will store the number of occurrences of pat in (txt+txt)[0 ... i].
There are two cases:
- When there is no full string txt present in level i. This means i< \mid txt \mid. There can be some proper prefix of txt whose length can be calculated as i \%\mid txt \mid. So, ans will be simply count_arr[ (i \%\mid txt \mid ) -1].
- When i>= \mid txt \mid. There will be (i/\mid txt \mid) full strings txt concatenated. The extra part will be some proper prefix of txt whose length can be calculated as i \%\mid txt \mid. So, contribution of extra part in ans can be calculated as follows. Since the extra part has a full txt preceding it.
We need occurrences of pat in txt+txt[0... (i \%\mid txt \mid ) -1] but we need to subtract the occurrences which are only in txt as we must have already calculated them (This is just contribution due to extra part not the full ans). Note the following code line. extra is nothing but i \%\mid txt \mid .
if(val){
ans=val*count1 + (val-1)*count3;
int extra = line % txt.size();
ans+= count_arr[txt.size()-1+extra]-count_arr[txt.size()-1];
}
else{
int extra = line % txt.size();
// cout<<extra<<endl;
ans= count_arr[extra-1];
}
To create count_arr, you just need to change the KMP function a little. I feel you can do this. You may look at the code for the details.
CPP Code
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vi;
vi computeLPSArray(string pat, int M);
vector<int> KMPSearch(string pat, string txt, int start)
{
int M = pat.size();
int N = txt.size();
vector<int> count_arr(N, 0);
vi lps = computeLPSArray(pat, M);
int i = 0;
int j = 0;
// int count = 0;
while (i < N) {
if(i){count_arr[i]=count_arr[i-1];}
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M && i>start) {
count_arr[i-1]+=1;
// count+=1;
j = lps[j - 1];
}
else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return count_arr;
}
vi computeLPSArray(string pat, int M)
{
int len = 0;
vi lps;
lps.push_back(0);
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps.push_back(len);
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
len = lps.at(len - 1);
}
else // if (len == 0)
{
lps.push_back(0);
i++;
}
}
}
return lps;
}
int main()
{
string pat, txt;
cin >> txt >> pat;
vector<int> count_arr; // count_arr[i] will tell occurances of pat in (txt+txt)[0...i]
int count1 = KMPSearch(pat, txt, 0)[txt.size()-1];
count_arr=KMPSearch(pat, txt + txt, 0);
int count2 = count_arr[2*txt.size()-1];
int count3 = count2 - 2*count1;
// cout<<count1<<" "<<count2<<endl;
int q;
cin >> q;
while(q--){
int line;
cin >> line;
int val=line/txt.size();
int ans=0;
if(val){
ans=val*count1 + (val-1)*count3;
int extra = line % txt.size();
ans+= count_arr[txt.size()-1+extra]-count_arr[txt.size()-1];
}
else{
int extra = line % txt.size();
// cout<<extra<<endl;
ans= count_arr[extra-1];
}
cout<<ans<<endl;
}
return 0;
}
Python Code
# Python program for KMP Algorithm
def KMPSearch(pat, txt, lps):
M = len(pat)
N = len(txt)
count_arr=[0 for x in range(N)]
# # create lps[] that will hold the longest prefix suffix
# # values for pattern
# lps = [0] * M
j = 0 # index for pat[]
# # Preprocess the pattern (calculate lps[] array)
# computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while i < N:
print(i)
count_arr[i]=count_arr[i-1]
print(count_arr[i-1])
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
# print(i)
count_arr[i-1]+=1
j = lps[j - 1]
# mismatch after j matches
elif i < N and 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 += 1
return count_arr
def computeLPSArray(pat, M):
lps=[0 for x in range(M)]
len = 0 # length of the previous longest prefix suffix
i = 1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i] == pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len - 1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
return lps
txt=input()
pat=input()
lps=computeLPSArray(pat,len(pat))
# print(lps)
count1=KMPSearch(pat,txt,lps)[-1]
count_arr=KMPSearch(pat,txt+txt,lps)
count2=count_arr[-1]
count3=count2-(2*count1)
q=int(input())
for _ in range(q):
n=int(input())
val=n//len(txt)
if val:
ans=val*count1 + (val-1)*count3
extra = n % len(txt)
ans+= count_arr[len(txt)-1+extra]-count_arr[len(txt)-1]
else:
extra=n%len(txt)
ans=count_arr[extra-1]
print(ans)
Also, to understand KMP (it’s tough actually!!) in detail, here is one good explanation-
2 Likes
The explanation was really helpful. I understood everything, thanks.
Any other TC?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=100005;
char s[MX],t[MX*3];
int pi[MX*3],a[MX],b[MX],c[MX*4];
void compute(int len,char s[],int pi[])
{
pi[0]=0;
for(int i=1;i<len;i++){
int j=pi[i-1];
while(j){
if(s[j]==s[i]){
pi[i]=j+1;
break;
}
j=pi[j-1];
}
if(j==0) pi[i]=(s[i]==s[0])?1:0;
}
}
int main()
{
int n,m,k,q;
scanf("%s %s %d",s,t,&q);
n=strlen(s),m=strlen(t);
strcat(t,"#");
strcat(t,s);
strcat(t,s);
compute(n+n+m+1,t,pi);
for(int i=0,j=m+1;i<n;i++,j++) a[i]=(pi[j]==m);
for(int i=0,j=n+m+1;i<m-1;i++,j++) b[i]=(pi[j]==m);
for(int i=1;i<n;i++){
a[i]+=a[i-1];
b[i]+=b[i-1];
}
//cout<<t<<"\n";
for(int i=1;i<=n+n+m+1;i++)
{
c[i]+=c[i-1];
if(pi[i-1]==m)
c[i]++;
//cout<<c[i]<<" ";
}
ll x,r;
while(q--){
scanf("%d",&k);
x=k/n,r=k%n;
if(x){
ll ans=x*(ll)c[m+1+n]+(x-1ll)*(ll)(c[n+m+1+m]-c[m+1+n]);
if(r) ans+=(ll)(c[m+1+r]);
if(r>0 && r<=m-1)
ans+=c[n+m+1+r]-c[n+m];
printf("%lld\n",ans);
}
else printf("%d\n",a[r-1]);
}
//cout<<x*c[m+n]<<" "<<(x-1)*(c[m+m+n]-c[m+n])<<" "<<c[m+r]<<" "<<c[m+n+r]-c[n+m];
return 0;
}
cccc
cc
1
5
I found the no of times t repeated in string s and string st formed from t.size()-1 letters from suffix of s and t.size()-1 letters from prefix of s and i found the no of times t occurs and stored it in pre1 array for string st. I tried all the test cases mentioned above but unable to find the mistake or the test case for which my code is giving wrong answer. Can anyone help me??
https://www.codechef.com/viewsolution/37040705
can anyone tell me what is wrong in my code?
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main(){
string s, t;
cin>>s>>t;
string ss = s;
ss += s;
int m = s.length(), p = t.length();
lli ans[2*m] = {0}, x;
for(int i = 0; i<=2*m-p; i++){
if(ss.substr(i, p)==t)ans[i+p-1]++;
}
for(int i = 1; i<2*m; i++)ans[i]+=ans[i-1];
x = ans[2*m-1]-2*ans[m-1];
lli n,q;
cin>>q;
while(q--){
cin>>n;
lli d = n/m;
lli r = n%m;
if(d>0){
d = d*ans[m-1] + (d-1)*x + ans[m+r-1]-ans[m-1];
}
else{
d = ans[r-1];
}
cout<<d<<"\n";
}
}
I thought this will throw TLE but get Accepted, why? I don’t know any of the prerequisites algorithm.
#include <bits/stdc++.h>
#include <string>
using namespace std;
typedef long long ll;
#define INF INT_MAX
#define fo(i, a, b) for (int i = a; i < b; i++)
#define fast_io \
ios::sync_with_stdio(0); \
cin.tie(0);
int t;
int patternOccurence(string str, string sub)
{
size_t found = 0;
int i = 0, x1 = 0;
while (found != string::npos)
{
found = str.find(sub, found + i);
if (found != string::npos)
{
x1++;
if (i == 0)
{
i++;
}
}
}
return x1;
}
void testCase()
{
string str, sub;
cin >> str;
cin >> sub;
string test = str + str;
int x1 = patternOccurence(str, sub);
int x2 = patternOccurence(test, sub);
int merge = x2 - 2 * x1;
int dp[str.length() + 1];
dp[0] = 0;
fo(i, 1, str.length() + 1)
{
dp[i] = -1;
}
ll Q, N;
cin >> Q;
fo(i, 0, Q)
{
cin >> N;
ll out = 0;
ll x = N / (str.length());
ll remainder = N % str.length();
out = x * x1;
if (x > 1)
{
out += (x - 1) * merge;
}
if (dp[remainder] == -1)
{
string temp = str + str.substr(0, remainder);
int tempcount = patternOccurence(temp, sub);
tempcount -= x1;
dp[remainder] = tempcount;
}
if (x == 0)
{
out -= merge;
}
out += dp[remainder];
cout << out << "\n";
}
}
int main()
{
fast_io;
// freopen("pin.txt", "r", stdin);
// freopen("pout.txt", "w", stdout);
t = 1;
while (t--)
{
testCase();
}
return 0;
}
Can anyone help me with this?
I think this is pretty straight forward solution but I am getting TLE for this. Am I doing something wrong in a while loop?
Can anyone please help and tell me why it is showing ‘‘wrong answer’’.
try:
s=input()
t=input()
for i in range(int(input())):
q=int(input())
s1=s*int(q/2)
lst_string=(s1[:q])
print(lst_string.count(t))
except:
pass
Can anyone help me to understand why i am getting TLE.
I am using KMP for String s,then s+s,then leftover and adding them,is there anything wrong with that?
int KMP(string s,string t)//KMP ALGORITHM
{
- int n=t.length();*
- int a[n];*
- int i=1,j=0;*
- a[0]=0;*
- while(i<n)*
- {*
-
if(t[i]==t[j])* -
{* -
a[i]=j+1;* -
i++;* -
j++;* -
}* -
else* -
{* -
a[i]=0;* -
j=a[i-1];* -
i++;* -
}* - }*
- i=0;*
- j=0;*
- int oc=0;*
- while(i<s.length())*
- {*
-
if(s[i]==t[j])* -
{* -
i++;* -
j++;* -
}* -
else if(j!=0)* -
{* -
j=a[j-1];* -
}* -
else* -
i++;* -
if(j==n)* -
{* -
oc++;* -
}* - }*
- return oc;*
}
// --solve function
void solve(string s,string t){ - int N;*
- cin>>N;*
- int n=s.length();*
- if(n!=0)*
- {*
- int x=N/n;*
- int y=N%n;*
- int c1=KMP(s,t);//occ in single string*
- int c2=KMP(s+s,t);//occ in conct string*
- int c3=c2-2c1;
- int c4=KMP(s+s.substr(0,y),t);//leftover string*
- int occ;*
- if(x==0)*
- occ=KMP(s.substr(0,y),t);*
- else*
- occ=((x-1)*c1)+((x-1)c3)+c4;
- cout<<occ<<endl;*
}}
// --main function
int main() {
- ios_base::sync_with_stdio(false);*
- cin.tie(NULL);*
- ll test = 1;*
- string s,t;*
- cin>>s>>t;*
- cin >> test;*
- while(test–) {*
- solve(s,t);*
- }*
- return 0;*
}
‘’’