Sign in to follow this  
AhmedCoeia

Understanding an algorithm solution

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this