最大对称字符串的算法
算法一:O(n^3)
判断字串是否对称是从外到里, O(n)
#include <stdio.h>
#include <string.h>
/*
*判断起始指针,到结束指针的字符串是否对称
*/
int IsSymmetrical(char* pBegin, char* pEnd)
{
if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
return 0;
while(pBegin < pEnd)
{
if(*pBegin != *pEnd)
return 0;
pBegin++;
pEnd--;
}
return 1;
}
/*
*查找最大对称字串长度,时间复杂度是O(n^3)
*/
int GetLongestSymmetricalLength(char* pString)
{
if(pString == NULL)
return 0;
int symmetricalLength = 1;
char* pFirst = pString;
int length = strlen(pString);
while(pFirst < &pString[length-1])
{
char* pLast = pFirst + 1;
while(pLast <= &pString[length-1])
{
if(IsSymmetrical(pFirst, pLast))
{
int newLength = pLast - pFirst + 1;
if(newLength > symmetricalLength)
symmetricalLength = newLength;
}
pLast++;
}
pFirst++;
}
return symmetricalLength;
}
int main()
{
char* str = "google";
int len = GetLongestSymmetricalLength(str);
printf("%d", len);
return 0;
}
算法2: O(n^2)
判断字串是否对称是从外到里, O(1)
#include <stdio.h>
#include <string.h>
int GetLongestSymmetricalLength(char* pString)
{
if(pString == NULL)
return 0;
int symmetricalLength = 1;
char* pChar = pString;
while(*pChar != '\0')
{
//奇数长度对称, 如 aAa
char* left = pChar - 1;
char* right = pChar + 1;
while(left >= pString && *right != '\0' && *left==*right)
{
left--;
right++;
}
int newLength = right - left - 1; //退出循环是*left!=*right
if(newLength > symmetricalLength)
symmetricalLength = newLength;
//偶数长度对称, 如 aAAa
left = pChar;
right = pChar + 1;
while(left >= pString && *right != '\0' && *left==*right)
{
left--;
right++;
}
newLength = right - left - 1; //退出循环是*left!=*right
if(newLength > symmetricalLength)
symmetricalLength = newLength;
pChar++;
}
return symmetricalLength;
}
int main()
{
char* str = "google";
int len = GetLongestSymmetricalLength(str);
printf("%d", len);
return 0;
}
算法3:manacher算法
原串:abaab
新串:#a#b#a#a#b#
这样一来,原来的奇数长度回文串还是奇数长度,偶数长度的也变成以‘#'为中心的奇数回文串了。
接下来就是算法的中心思想,用一个辅助数组P记录以每个字符为中心的最长回文半径,也就是P[i]记录以Str[i]字符为中心的最长回文串半径。P[i]最小为1,此时回文串为Str[i]本身。
我们可以对上述例子写出其P数组,如下
新串: # a # b # a # a # b #
P[] : 1 2 1 4 1 2 5 2 1 2 1
我们可以证明P[i]-1就是以Str[i]为中心的回文串在原串当中的长度。
证明:
1、显然L=2*P[i]-1即为新串中以Str[i]为中心最长回文串长度。
2、以Str[i]为中心的回文串一定是以#开头和结尾的,例如“#b#b#”或“#b#a#b#”所以L减去最前或者最后的‘#'字符就是原串中长度的二倍,即原串长度为(L-1)/2,化简的P[i]-1。得证。
注: 不是很懂, 自己改了
#include <stdio.h>
#include <string.h>
int GetLongestSymmetricalLength(char* pString)
{
int length = strlen(pString);
char* pNewString = malloc(2*length+2);
int i;
for(i=0; i<length; i++)
{
*(pNewString+i*2) = '#';
*(pNewString+i*2+1) = *(pString+i);
}
*(pNewString+2*length) = '#';
*(pNewString+2*length+1) = '\0';
printf("%s\n", pNewString);
int maxLength = 1;
char* pChar;
for(i=0; i<2*length+2; i++)
{
int newLength = 1;
pChar = pNewString + i;
char* left = pChar-1;
char* right = pChar+1;
while(left>=pNewString && *right!='\0'&& *left==*right)
{
left--;
right++;
newLength++;
}
if(newLength > maxLength)
maxLength = newLength;
}
return maxLength-1;
}
int main()
{
char* str = "google";
int len = GetLongestSymmetricalLength(str);
printf("%d", len);
return 0;
}
相关文章
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章介绍了C#判断字符串是否数字或字母的实例,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了PostgreSQL判断字符串是否包含目标字符串的多种方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文实例讲述了php字符串按照单词进行反转的方法。分享给大家供大家参考。具体分析如下:下面的php代码可以将字符串按照单词进行反转输出,实际上是现将字符串按照空格分隔到数组,然后对数组进行反转输出。...2015-03-15
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了MySQL 字符串拆分操作(含分隔符的字符串截取),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-22
- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- JS中默认中文字符长度和其它字符长度计算方法是一样的,但某些情况下我们需要获取中文字符串的实际长度,代码如下: 复制代码 代码如下: function strLength(str) { var realLength = 0, len = str.length, charCode = -1;...2014-06-07
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
- 文章介绍一个实用的函数,我们如果用php substr来截取字符在中文上处理的很有问题,今天自己写了一个比较好的中文与英文字符截取的函数,有需要的朋友可以参考下。 ...2016-11-25
- 这篇文章主要介绍了C#实现对字符串进行大小写切换的方法,涉及C#操作字符串的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#将字节数组转成易读的字符串的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了PostgreSQL 字符串处理与日期处理操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-01
- 这篇文章主要介绍了C#获取字符串后几位数的方法,实例分析了C#操作字符串的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了Substring截取字符串方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 在网站开发中,我们经常使用php similar text 计算两个字符串相似度;1,similar_text的用法 如果我想计算"ly89cn"和"ly89"的相似程度,有两种表示方法复制代码 代码如下: echo similar_text('ly89cn', 'ly89'); ...2015-11-08
- 这篇文章主要介绍了C#实现将字符串转换成日期格式的方法,涉及C#操作时间及字符串的相关技巧,非常简单实用,需要的朋友可以参考下...2020-06-25
- 在串口通讯过程中,经常要用到 16进制与字符串、字节数组之间的转换...2020-06-25