PROBLEM LINK:
Author & Editorialist: Aman Dwivedi
Tester: Jatin Nagpal
DIFFICULTY:
EASY
PREREQUISITES:
KMP Algorithm/Z Algorithm/String Hashing and Prefix Array
Problem
Given a string S that forms a pyramid of infinite length. You need to answer Q queries, the answer to each query is the number of occurrences of string T in particular row of that pyramid.
EXPLANATION:
Initial thoughts
Let us find the number of occurrences of string T in string S, name it c1. Now concatenate the string S with itself, and now find the number of occurrences of string T in this concatenated string, name it c2.
Is c2=2*c1 ?
No as due to concatenation, the number of occurrences can increase. Also concatenating only once is enough as the size of T is always smaller than or equal to size of S.
Finding number of occurrences
First we find the number of occurrences of string T in string S by using any pattern matching algorithm, name it c1.
Now concatenate string S with itself and find the the number of occurrences of string T in this concatenated string, name it c2
Extra occurrences, if any can be found by c3 = c2-2*c1.
Answering Queries
Find the number of times S appears in given row. This can be found by dividing the given row number by the size of S, say it x.
This means (x-1) times the string is concatenated. So the number of occurrences will be (x * c1 + (x-1) * c3).
Still some characters will be left i.e. (x % |S|). Check whether these characters results in some extra occurrences, it can be found by maintaining a prefix array at start.
Well take care when x comes out to be 0. Try to handle this case seperately.
SOLUTIONS:
Using KMP Algorithm
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,a,n) for(int i=a;i<=n;i++)
#define repb(i,a,n) for(int i=a;i>=n;i--)
#define trav(a,x) for(auto a=x.begin();a!=x.end();a++)
#define all(x) x.begin(),x.end()
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
typedef long double ld;
typedef pair <int,int> pii;
typedef vector <int> vi;
typedef long long ll;
void pre(){
}
vi prefix_function(string const &s){
int n=s.size();
vi pi(n);
pi[0]=0;
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j>0 && s[i]!=s[j])
j=pi[j-1];
pi[i]=j+(s[i]==s[j]);
}
return pi;
}
void solve(){
string s; cin>>s;
string t; cin>>t;
int c1=0,c2=0;
string temp=t+'#'+s+s;
vi pi=prefix_function(temp);
int count[2*s.size()];
int j=0;
for(int i=t.size()+1;i<(temp.size());i++){
if(i==t.size()+1){
if(pi[i]==(t.size())){
c1++;
c2++;
count[j]=1;
}
else count[j]=0;
}
else{
if(pi[i]==(t.size())){
if(i>(s.size()+t.size())){
c2++;
}
else{
c1++;
c2++;
}
count[j]=count[j-1]+1;
}
else{
count[j]=count[j-1];
}
}
j++;
}
int con=(c2-(2*c1));
int q; cin>>q;
while(q--){
ll n; cin>>n;
ll ans=0;
ll quot=n/(s.size());
if(quot!=0){
ll rem=n%(s.size());
ans+=((quot*c1)+((quot-1)*con));
if(rem!=0){
ans+=(count[s.size()+rem-1]-count[s.size()-1]);
}
}
else{
ll rem=n%(s.size());
ans+=(count[rem-1]);
}
cout<<ans<<endl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
pre();
int t; t=1;
rep(i,t) solve();
return 0;
}
Using Z Algorithm
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod=1000000007;
const int INF=1e18;
vector<int> z_function(string s) {
int n = (int) s.length();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r)
z[i] = min (r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}
int pre[300005];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s,t;
cin>>s>>t;
int sl=s.length();
int tl=t.length();
string a=t+"#"+s+s;
vector <int> b=z_function(a);
for(int i=0;i<sl;i++) {
if(b[i+tl+1]==tl) {
pre[i+tl]++;
}
}
for(int i=1;i<=2*sl;i++) {
pre[i]+=pre[i-1];
}
int q;
cin>>q;
while(q--) {
int in;
cin>>in;
if(in<=sl) {
cout<<pre[in]<<'\n';
}
else {
int ans=0;
in-=sl+1;
ans=in/sl;
in-=ans*sl;
ans*=pre[2*sl];
in+=sl+1;
ans+=pre[in]+pre[in-sl];
cout<<ans<<'\n';
}
}
return 0;
}
Using String Hashing
#include <bits/stdc++.h>
using namespace std;
#define int long long
int A = 911382323, B = 972663749;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s, t;
cin >> s >> t;
int shash[2*s.size()], pref[2*s.size()];
int i, j, q, a=1;
int Apow[2*s.size()], modinv[2*s.size()+1];
Apow[0] = 1;
for(i=1; i<2*s.size(); i++){
Apow[i] = Apow[i-1]*A;
Apow[i] %= B;
}
for(i=0; i<=2*s.size(); i++){
modinv[i] = binpow(Apow[i], B-2, B);
modinv[i] %= B;
}
for(i=0; i<2*s.size(); i++){
shash[i] = s[i%s.size()]*a % B;
a *= A;
a %= B;
}
pref[0] = shash[0];
for(i=1; i<2*s.size(); i++){
pref[i] = pref[i-1]+shash[i];
pref[i] %= B;
}
int thash = 0;
a = 1;
for(i=0; i<t.size(); i++){
thash += t[i]*a % B;
thash %= B;
a *= A;
a %= B;
}
int inside = 0, across = 0;
int reminside[s.size()]={0}, remacross[s.size()]={0};
if(pref[t.size()-1] == thash){
inside++;
reminside[t.size()-1] = inside;
}
for(i=t.size(); i<s.size(); i++){
int sum = (pref[i] - pref[i-t.size()]+B)%B;
sum *= modinv[i-t.size()+1];
sum %= B;
if(thash == sum){
inside++;
}
reminside[i] = inside;
}
for(i=s.size()-t.size()+1; i<s.size(); i++){
int sum = (pref[i+t.size()-1] - pref[i-1]+B)%B;
sum *= modinv[i];
sum %= B;
if(thash == sum){
across++;
}
remacross[(i+t.size())%s.size() - 1] = across;
}
if(t.size() != 1){
for(i=t.size()-1; i<s.size(); i++){
remacross[i] = remacross[i-1];
}
}
cin >> q;
while(q--){
int n;
cin >> n;
int whole = n/s.size();
int ans = inside*whole + across*(max(0ll, whole-1));
if(n%s.size() == 0){
cout << ans << "\n";
continue;
}
ans += reminside[n%s.size()-1];
if(whole == 0){
cout << ans << "\n";
continue;
}
ans += remacross[n%s.size()-1];
cout << ans << "\n";
}
}
and my first contest gone really well. Good work guys.