QUERYSTR - Query Problem SPOJ Solution C++

➤  Problem Link : QUERYSTR 

👉 Hint : Use Z Algorithm

 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

int Z[1000001];

void CalCZ(string s)
{
	Z[0]=s.length();
	int l=0,r=0;
	for(int i=1;i<s.length();i++)
	{
		if(i>r)
		{
			l=i;
			r=i;
			while(r<s.length() && s[r]==s[r-l])
			{
				r++;
			}	
			Z[i]=r-l;
			r--;
		}
		else
		{
			int k=i-l;
			if(Z[k]<r-i+1)
				Z[i]=Z[k];
			else
			{
				l=i;
				while(r<s.length() && s[r]==s[r-l])
					r++;
				Z[i]=r-l;
				r--;
			}
		}
    
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t,n,x;
	string s;
	cin>>t;
	while(t--)
	{
		cin>>s;
		reverse(s.begin(),s.end());
		CalCZ(s);
		cin>>n;
		while(n--)
		{
			cin>>x;
			cout<<Z[s.length()-x]<<"\n";
		}
	}
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.