'Urgent! Need help finding algorithm' Thread RSS Feed

Urgent! Need help finding algorithm

Tue, 14 May 2002 02:18:00 -0700

I have an assignment about finding the algorithm of carcinoid phrases like "Anna" or something like "Pollop", words that can be spelled the same backwards. I have created one of my one but it is too scratchy for my proffesor. If anyone can help sending an URL please do, i need it yesterday!
I also need additional information about these phrases. I have been over 6 hours on search engines and i have found nothing. I need help finding resources so if anyone can help i would appreciate it very much :))
Thank you

Re: Urgent! Need help finding algorithm

Tue, 14 May 2002 07:44:12 -0700

The words you are referring to are called palindroms. I assume you are trying to determine if a given string is a palindrom. To do this, you create a string that is the reverse of the other, set the case on both of them to be the same, and use string.equal(string) to see if they are the same. To reverse the string, simply loop through the string one character at a time and place it at the beginning of a temporary string, such as:

while (i < str1.length())
    str2 = str1.charAt(i) + str2;
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
return str1.equals(str2);

I wrote this code using Java, which has these methods at my disposal. If you don't have these methods, then you would have to parse the original string one character at a time, and then store the character at the beginning of one string and at the end of another:

while (myStr != null)
{   Char c = myStr.substring(0,1);
    myStr = myStr.subString(1);
    str1 = str1 + c;
    str2 = c + str2;
}
while (str1 != null)
{   Char c1 = str1.substring(0,1);
    Char c2 = str2.substring(0,1);
    str1 = str1.substring(1);
    str2 = str2.substring(1);
    if (c1 != c2)
    {   retValue = false;
        str1 = null;
    }
}
return retValue;

I can't think of any other way to do this right now, but if one comes to me, I'll let you know.

If you have enough memory, you won't have enough disk space.

Re: Urgent! Need help finding algorithm

Fri, 28 Jun 2002 12:33:24 -0700

There is a website that has weekly programming competitions that was mentioned elsewhere that has an algo for finding palindromes.

http://www.geocities.com/acmesofties/

All code in C

The week 1 answer was

int ispalin(char *a,int st,int end)
{
 return (st>=end)?1:(a[st]==a[end])?ispalin(a,st+1,end-1):0;
}

But you could also try this:

int IsPalin(char *s)
{
  int i, j = 0;
  for(i = 0; s[i]; i++) ;
  while(s[--i] == s[j] && i > ++j) ;
  return j >= i;
}