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…