Understanding an algorithm solution

This topic is 1865 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I wanted to solve the problem here on my own: To find the longest substring with equal sum in left and right in C++ http://stackoverflow.com/questions/8469407/to-find-the-longest-substring-with-equal-sum-in-left-and-right-in-c
The code is here
[code]
int getEqualSumSubstring(string s) {
int i=0,j=i,foundLength=0;
for(i=0;i<s.length();i++)
{
for(j=i;j<s.length();j++)
{
int temp = j-i+1;
if(temp%2==0)
{
int leftSum=0,rightSum=0;
string tempString=s.substr(i,temp);
// printf("%d ",tempString.length());
for(int k=0;k<temp/2;k++)
{
leftSum=leftSum+tempString[k]-48;
rightSum=rightSum+tempString[k+(temp/2)]-48;
}
if((leftSum==rightSum)&amp;&amp;(leftSum!=0))
if(tempString.length()>foundLength)
foundLength=tempString.length();
}
}
}
return(foundLength);
}
[/code]
I wanted to know how the calculation of temp = i+j-1 is done ? how on paper or by examples he could get that equation. I tried a lot but I couldn't get it. Edited by AhmedCoeia

Share on other sites
Please use [ code ][ /code ] (without spaces) tags (to get pretty formatted code)! I'll recreate it here in the meantime:

[code]int getEqualSumSubstring(string s) {
int i=0,j=i,foundLength=0;
for(i=0;i<s.length();i++)
{
for(j=i;j<s.length();j++)
{
int temp = j-i+1;

if(temp%2==0)
{
int leftSum=0,rightSum=0;
string tempString=s.substr(i,temp);
// printf("%d ",tempString.length());
for(int k=0;k<temp/2;k++)
{
leftSum=leftSum+tempString[k]-48;
rightSum=rightSum+tempString[k+(temp/2)]-48;
}
if((leftSum==rightSum)&&(leftSum!=0))
if(tempString.length()>foundLength)
foundLength=tempString.length();
}
}
}
return(foundLength);
}
[/code]

I'd help analyze it but I've got to study for some finals [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img]

Share on other sites
I just need the part with int temp = i+j-1. How it was done by picture or by some examples...

Share on other sites
Why did you mention temp = i + j - 1 two times?
It is temp = j - i + 1, which is the character count between index i and j.
The algorithm is extract every sub string and compare the sum at even and odd indexes.

Share on other sites
I don't know how the calculation is done to say temp = j-i+1. I can't visualize it.

Share on other sites
Let's state in plain text what the outer shell of the algorithm does:
For each offset [font=courier new,courier,monospace]i[/font] in the string - take successively larger substrings of even length from that offset, until the end of the string is reached.
[font=courier new,courier,monospace]i[/font] is the left index of the substring, inclusive.
[font=courier new,courier,monospace]j[/font] is the right index of the substring, inclusive. [font=courier new,courier,monospace]j+1[/font] is the right index of the string, exclusive

We cannot immediately use [font=courier new,courier,monospace]j[/font] in our expressions, as we want to both find out if a substring is even and the [font=courier new,courier,monospace]substring(off,n)[/font] function takes an absolute count [font=courier new,courier,monospace]n[/font] of characters.

We can set up an equation to find the length from [font=courier new,courier,monospace]i[/font] and [font=courier new,courier,monospace]j[/font], looking for "what number must we add to [font=courier new,courier,monospace]i[/font] to get the index of one character to the right of [font=courier new,courier,monospace]j[/font]":
[font=courier new,courier,monospace]i + len = j + 1[/font]
[font=courier new,courier,monospace]len = j + 1 - i[/font]
[font=courier new,courier,monospace]len = j - 1 + 1[/font]