That TLE is due to complexity of your code being O(Q \cdot (\mid T \mid+N) ) . Try to find an optimized solution and why are you calculating count1 and count2 for each query while these don’t depend on the query in any way. Fixing this will still give you TLE as you’re still calculating count4 in for each query. The worst case complexity will still remain the same.
There are two type of occurances of T:
- the occurance that starts and ends at the same S.
- the occurance that starts at the previous S and ends at the current S (like you said when two S are combined we get this type of occurances).
The array a counts only first type of occurances and the array b counts only second type of occurances. So in your example, the occurances which are entirely contained in the second S, aren’t counted in the term (x-1)*b[n-1] , they are counted in the term x*a[n-1] . So I don’t need to subtract anything.
In your implementation, I think you tried to count second type of occurances using the term (x-1ll)*(ll)(c[n+m+1+n-1]-c[m+1+n-1]) , but that’s wrong. Bacause this term counts some first type occurances too.
1 Like
(x-1ll)*(ll)(c[n+m+1+m-1]-c[m+1+n-1])
What if I use this? I understood my first doubt.
But count4 will have to be calculated for each query separately right as it depends on the query?
Why to use another kmp search to calculate count4 ?
count4 denotes the number of occurrences of T in S+ (some prefix of S). Right? You can do some pre-calculations.
I am using count4 to count any occurence that starts at the previous S and ends at the current S. Could you pleases suggest a method as I have just learnt this KMP algorithm and unable to figure which way I can do those pre-calculations 
.
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;*
}
‘’’