c - Effective way of checking if a given string is palindrome in C

Question

I was preparing for my interview and started working from simple C programming questions. One question I came across was to check if a given string is palindrome. I wrote a a code to find if the user given string is palindrome using Pointers. I'd like to know if this is the effective way in terms of runtime or is there any enhancement I could do to it. Also It would be nice if anyone suggests how to remove other characters other than letters (like apostrophe comas) when using pointer.I've added my function below. It accepts a pointer to the string as parameter and returns integer.

int palindrome(char* string)
{
    char *ptr1=string;
    char *ptr2=string+strlen(string)-1;
    while(ptr2>ptr1){
        if(tolower(*ptr1)!=tolower(*ptr2)){
            return(0);
        }
        ptr1++;ptr2--;
    }
    return(1);
}

Answer 1

“如何去除字母以外的其他字符？”

我认为您不想实际删除它，只需跳过它，您就可以isalpha这样做。另请注意，条件ptr2 > ptr1仅适用于具有偶数字符的字符串，例如abba，但对于诸如 的字符串abcba，条件应为ptr2 >= ptr1：

int palindrome(char* string)
{
    size_t len = strlen(string);

    // handle empty string and string of length 1:
    if (len == 0) return 0;
    if (len == 1) return 1;

    char *ptr1 = string;
    char *ptr2 = string + len - 1;
    while(ptr2 >= ptr1) {
        if (!isalpha(*ptr2)) {
            ptr2--;
            continue;
        }
        if (!isalpha(*ptr1)) {
            ptr1++;
            continue;
        }
        if( tolower(*ptr1) != tolower(*ptr2)) {
            return 0;
        }
        ptr1++; ptr2--;
    }
    return 1;
}

你可能需要#include <ctype.h>

Answer 2

如果您只想使用指针来做这样的事情：

int main()
{
 char str[100];
 char *p,*t;
 printf("Your string : ");
 gets(str);
 for(p=str ; *p!=NULL ; p++);
  for(t=str, p-- ; p>=t; )
  {
    if(*p==*t)
    {
        p--;
        t++;
    }
    else
        break;
  }
  if(t>p)
       printf("\nPalindrome");
  else
       printf("\nNot a palindrome");
  getch();
  return 0;
}

Answer 3

int main()
{   

const char *p = "MALAYALAM";

int count = 0;
int len = strlen(p);
for(int i = 0; i < len; i++ )
{
    if(p[i] == p[len - i - 1])
        count++;
}

cout << "Count: " << count;
if(count == len)
    cout << "Palindrome";
else
    cout << "Not Palindrome";

return 0;
}

Answer 4

我实际上已经对这种问题进行了很多实验。

可以进行两种优化：

• 检查奇串长度，奇串不能是回文
• 开始使用向量化比较，但这只有在您期望有很多回文时才能真正给您带来性能。如果您的大多数字符串不是回文，那么您仍然最好进行逐字节比较。事实上，我的向量化回文检查器比非向量化的运行速度慢 5%，因为回文在输入中非常罕见。决定矢量化与非矢量化的额外分支产生了很大的不同。

这是代码草稿，您可以如何对其进行矢量化：

int palindrome(char* string)
{
    size_t length = strlen(string);

    if (length >= sizeof(uintptr_t)) { // if the string fits into a vector
        uintptr_t * ptr1 = (uintptr_t*)string;
        size_t length_v /= sizeof(uintptr_t);
        uintptr_t * ptr2 = (uintptr_t*)(string + (length - (length_v * sizeof(uintptr_t)))) + length_v - 1;

        while(ptr2>ptr1){
            if(*ptr1 != bswap(*ptr2)){ // byte swap for your word length, x86 has an instruction for it, needs to be defined separately
                return(0);
            }
            ptr1++;ptr2--;
        }

    } else {
        // standard byte by byte comparison
    }
    return(1);
}