substring matching

Given a string S and and integer K, find the integer C which equals the number of pairs of substrings(S1,S2) such that S1 and S2 have equal length and Mismatch(S1, S2) <= K where the mismatch function is defined below.

mismatch(abc,abs)=1 c and s are diffrent;
i have brute force this but i need optimal solution…

 int mismatch(string s1,string s2)
        {
      int l1=s1.length();
      int l2=s2.length();
     int ans=0;
     int i=0;
      if(l1==l2)
             {
	   
	while(s1[i]!='\0')
	{
		if(s1[i]!=s2[i])
		{
			ans++;
		}
		i++;
	}
	
}
 
return ans;

}
main()
{

             int K;
             string s;
                cin>>K;
            cin>>s;
         int len=s.length();
          vector<string> v[5005];
            int count=0;
          for(int i=0;i<s.length();i++)
          {
	string str;
	for(int j=i;j<s.length();j++)
	{
		str+=s[j];
		for(int k=i+1;k<s.length();k++)
		{
			                      if((str.length()==s.substr(k,str.size())).length())&&mismatch(str,s.substr(k,str.size()))<=K)
			{
				count++;
			}
			
		}
		
	
	}
}
cout<<count;

plz help me to otimize this…


People dont solve it,it is an ongoing contest question.

1 Like
//