EQSBSTR1 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Simple

PREREQUISITES:

Strings

PROBLEM:

You are given two strings A and B of lengths N and M respectively. Find the maximum length of a substring of A that is also present in B. Let this maximum length be K. Also, find all such substrings of length K that is present in both A and B and print the number of times each such substring occurs in B.

EXPLANATION:

You can just brute force all substrings of A from largest to smallest. And as soon as we find a match in B, we print all matching substrings of that length and their counts in B. We do not need to check any further, because we have now found all matching substrings of the maximum length.

Refer to the solutions below if you face any problem.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()

using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input1.txt","r",stdin);
    // freopen("outputE1.txt","w",stdout);
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n,m,i,j,k;
        cin>>n>>m;
        string a,b;
        cin>>a>>b;
        set<pair<string,ll> > ans;
        for(k=n;k>=1;k--)
        {
            for(i=0;i<n-k+1;i++)
            {
                string tmp=a.substr(i,k);
                ll cnt=0;
                for(j=0;j<m-k+1;j++)
                {
                    if(tmp == b.substr(j,k))
                        cnt++;
                }
                if(cnt) ans.insert({tmp,cnt});
            }
            if(ans.size()) break;
        }
        cout<<k<<"\n";
        for(auto it:ans)
            cout<<it.F<<" "<<it.S<<"\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
bool check(int sz,string a,string b)
{
	if(sz==0)return true;
 
	set<string> sA;
	for(int i=0;i+sz-1<a.size();i++)
		sA.insert(a.substr(i,sz));
	for(int i=0;i+sz-1<b.size();i++)
		if(sA.find(b.substr(i,sz))!=sA.end())
			return true;
	return false;
}
int main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifdef Zoro
   freopen("/home/pritish/Competitive/in", "r", stdin);
   freopen("/home/pritish/Competitive/out", "w", stdout);
   #endif  
   
   int t,sumn=0,summ=0;
   cin>>t;
   assert(t>=1&&t<=100);
 
   while(t--)
   {
   		int n,m;
   		cin>>n>>m;
 
   		assert(n>=1&&n<=20);
   		assert(m>=1&&m<=20);
   		sumn+=n;
   		summ+=m;
   		assert(sumn<=1000);
   		assert(summ<=1000);
 
   		string a,b;
   		cin>>a>>b;
 
   		assert(a.size()==n);
   		assert(b.size()==m);
   		for(auto x:a)assert(x>='a'&&x<='z');
   		for(auto x:b)assert(x>='a'&&x<='z');
   		
 
 
   		int lo=0,hi=min(n,m),k=0;
   		while(lo<=hi)
   		{
   			int mid=(lo+hi)/2;
   			if(check(mid,a,b))
   			{
   				k=mid;
   				lo=mid+1;
   			}
   			else hi=mid-1;
   		}
 
   		cout<<k<<'\n';
   		if(k==0)continue;
 
   		set<string> sA;
   		map<string,int> mA;
 
		for(int i=0;i+k-1<a.size();i++)
			sA.insert(a.substr(i,k));
		for(int i=0;i+k-1<b.size();i++)
			if(sA.find(b.substr(i,k))!=sA.end())
				mA[b.substr(i,k)]++;
 
		for(auto x:mA)
		{
			cout<<x.first<<" "<<x.second<<'\n';
		}
 
 
   }
 
   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}

Feel free to write your approach in the comments :slight_smile:

2 Likes