View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Understanding an algorithm solution

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

#1AhmedCoeia  Members

Posted 10 December 2012 - 11:00 PM

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
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);
}

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, 10 December 2012 - 11:12 PM.

#2Cornstalks  Members

Posted 10 December 2012 - 11:06 PM

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

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);
}


I'd help analyze it but I've got to study for some finals
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#3AhmedCoeia  Members

Posted 10 December 2012 - 11:13 PM

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

#4wqking  Members

Posted 10 December 2012 - 11:53 PM

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.

http://www.cpgf.org/
cpgf library -- free C++ open source library for reflection, serialization, script binding, callbacks, and meta data for OpenGL Box2D, SFML and Irrlicht.
v1.5.5 was released. Now supports tween and timeline for ease animation.

#5AhmedCoeia  Members

Posted 11 December 2012 - 03:52 AM

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

#6Zao  Members

Posted 11 December 2012 - 05:11 PM

Let's state in plain text what the outer shell of the algorithm does:
For each offset i in the string - take successively larger substrings of even length from that offset, until the end of the string is reached.
i is the left index of the substring, inclusive.
j is the right index of the substring, inclusive. j+1 is the right index of the string, exclusive

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

We can set up an equation to find the length from i and j, looking for "what number must we add to i to get the index of one character to the right of j":
i + len = j + 1
len = j + 1 - i
len = j - 1 + 1
To make it is hell. To fail is divine.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.