找源字符串的最长回文子串（通过vc编译能够正常运行）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

回文字符串：即从前往后读，和从后往前读为一样的结果的字符串

我们不正面用蛮力法解决这个问题，通过回文字符串的定义，可以将该问题转换为将源字符串反转，

求源字符串和反转字符串的最长连续公共子串。代码实现如下：

#include

#include

#include

char *search_max_repeatstr(char *src)

{

char tmp[256] = {0};

int len = strlen(src);

int i,j,k,count=0;

int t;

/*判断参数合法性*/

if (src == NULL || len <2)

{

return src;

}

/*反转字符串*/

for (k=0;k

{

tmp[k] = src[len-k-1];

}

tmp[len] = '\0';

/*查找最大连续公共子串，i表示每次需要匹配的长度，从最大长度len开始取，不能匹配这个长度则

将其递减，当能够匹配i个字符时，返回子串为所求*/

for (i=len;i>0;i--)

{

count = 0;

k = 0;

j = 0;

/*错位式匹配两个字符串，遍历所有的情况*/

for (j=0;j

{

t=j;

/*将反转字符串中的字符与src[t]匹配，不能匹配，则更新t的值直到遍历整个src数组；

 否则，确认是否能够连续匹配i个，如果能够连续匹配i个则将字符串截断，返回回文

 子串，不能连续匹配i个字符则将计数清零，继续匹配*/

for(k=0; k

{

if (tmp[k] == src[t])

{

count++;

if (count == i)

{

src[t+1] = '\0';

return &src[t-i+1];

}

t++;

}

else

{

count = 0;

}

}

}

}

return NULL;

}

int main(void)

{

char src[256] ="abcdefghhgfeuih";

char *tmp=NULL;

tmp = search_max_repeatstr(src);

printf("tmp=%s\n", tmp);

return 0;

}

阅读(1749) | 评论(0) | 转发(0) |

0

上一篇：笔试面试怪题解题思路汇总

下一篇：atoi的实现以及判断ip地址是否合法的的实现（某公司技术面）