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)&&(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.
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.
https://github.com/cpgf/cpgf cpgf library -- free C++ open source library for reflection, serialization, script binding, callbacks, and meta data for OpenGL Box2D, SFML and Irrlicht.
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]
