【题 目】输入一个字符串,输出该字符串中最大对称子串的长度。例如输入字符串:“google”,该字符串中最长的子字符串是“goog”,长度为4,因而输出为4。
【思 路1】一看这题就是遍历!没错,我们最直观的往往也是最容易实现的,这里我们暂且不考虑效率的问题。我们的基本思路是:我们如果有一个判断一个字符串是不是对称的函数的话,我们就可以用这个子函数逐一检查原字符串中所有的字符串,然后输出长度最大的即可。
(1)怎样判断一个字符串是不是对称的字符串?我们可以用两个指针分别指向字符串的第一个字符和最后一个字符,判断是否相等,如果不等直接返回false,如果为真则接着比较下一对字符。(2)如果遍历遍历原字符串的所有子串,首先我们让一个指针从头至尾遍历,对于这个指针的每一个字符,我们在用另一个指针逐一指向它后面的每一个字符即可。好了,两个问题都解决了,我们可以写出如下的代码:
解法一:O(n3)的算法
现在我们试着来得到对称子字符串的最大长度。最直观的做法就是得到输入字符串的所有子字符串,并逐个判断是不是对称的。如果一个子字符串是对称的,我们就得到它的长度。这样经过比较,就能得到最长的对称子字符串的长度了。于是,我们可以写出如下代码:
// IsSymmetricalString2.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/************************************************
* 判断一个字符串是否是对称的
*************************************************/
bool IsSymmetricalString(char* pstart,char* pend)
{
if (pstart==NULL || pend==NULL || pstart>pend)
{
return false;
}
while (pstart<pend)
{
if (*pstart!=*pend)
{
return false;
}
pstart++;
pend--;
}
return true;
}
/*************************************************
* 求最大对称子串的长度
**************************************************/
int MaxSymmetricalSubstringLenth(char *pstring)
{
if (pstring==NULL)
{
return 0;
}
int maxLength=1;
int length=strlen(pstring);
char* pstart=pstring;
while (pstart<&pstring[length-1])
{
char* psecond=pstart+1;
while (psecond<=&pstring[length-1])
{
if (IsSymmetricalString(pstart,psecond))
{
int tempLength=psecond-pstart+1;
if (tempLength>maxLength)
{
maxLength=tempLength;
}
}
psecond++;
}
pstart++;
}
return maxLength;
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"Please Enter Your String(the length must <1000 ):"<<endl;
char* yourstring = new char[1000];
cin>>yourstring;
cout<<"The Max Symmetrical SubString Length in Your String is:"<<endl;
cout<<MaxSymmetricalSubstringLenth(yourstring)<<endl;
system("pause");
return 0;
}
// IsSymmetricalString2.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/************************************************
* 判断一个字符串是否是对称的
*************************************************/
bool IsSymmetricalString(char* pstart,char* pend)
{
if (pstart==NULL || pend==NULL || pstart>pend)
{
return false;
}
while (pstart<pend)
{
if (*pstart!=*pend)
{
return false;
}
pstart++;
pend--;
}
return true;
}
/*************************************************
* 求最大对称子串的长度
**************************************************/
int MaxSymmetricalSubstringLenth(char *pstring)
{
if (pstring==NULL)
{
return 0;
}
int maxLength=1;
int length=strlen(pstring);
char* pstart=pstring;
while (pstart<&pstring[length-1])
{
char* psecond=pstart+1;
while (psecond<=&pstring[length-1])
{
if (IsSymmetricalString(pstart,psecond))
{
int tempLength=psecond-pstart+1;
if (tempLength>maxLength)
{
maxLength=tempLength;
}
}
psecond++;
}
pstart++;
}
return maxLength;
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"Please Enter Your String(the length must <1000 ):"<<endl;
char* yourstring = new char[1000];
cin>>yourstring;
cout<<"The Max Symmetrical SubString Length in Your String is:"<<endl;
cout<<MaxSymmetricalSubstringLenth(yourstring)<<endl;
system("pause");
return 0;
}
我们来分析一下上述方法的时间效率。由于我们需要两重while循环,每重循环需要O(n)的时间。另外,我们在循环中调用了IsSymmetrical,每次调用也需要O(n)的时间。因此整个函数的时间效率是O(n3)。
通常O(n3)不会是一个高效的算法。如果我们仔细分析上述方法的比较过程,我们就能发现其中有很多重复的比较。假设我们需要判断一个子字符串具有aAa的形式(A是aAa的子字符串,可能含有多个字符)。我们先把pFirst指向最前面的字符a,把pLast指向最后面的字符a,由于两个字符相同,我们在IsSymtical函数内部向后移动pFirst,向前移动pLast,以判断A是不是对称的。接下来若干步骤之后,由于A也是输入字符串的一个子字符串,我们需要再一次判断它是不是对称的。也就是说,我们重复多次地在判断A是不是对称的。
造成上述重复比较的根源在于IsSymmetrical的比较是从外向里进行的。在判断aAa是不是对称的时候,我们不知道A是不是对称的,因此需要花费O(n)的时间来判断。下次我们判断A是不是对称的时候,我们仍然需要O(n)的时间。
解法二:O(n2)的算法
如果我们换一种思路,我们从里向外来判断。也就是我们先判断子字符串A是不是对称的。如果A不是对称的,那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果A对称,那么我们只需要判断A两端延长的一个字符是不是相等的,如果相等,则延长后的字符串是对称的。因此在知道A是否对称之后,只需要O(1)的时间就能知道aAa是不是对称的。
我们可以根据从里向外比较的思路写出如下代码
// MaxSymmetricalSubstringLenth.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
/*********************************************************************
* 计算字符串最大对称子串的长度
*********************************************************************/
int GetLongestSymmetricalLength_2(char* pString)
{
if(pString == NULL)
return 0;
int symmeticalLength = 1;
char* pChar = pString;
while(*pChar != '\0')
{
// Substrings with odd length(奇数)
char* pFirst = pChar - 1;
char* pLast = pChar + 1;
while(*pLast != '\0' && *pFirst == *pLast)
{
pFirst--;
pLast++;
}
int newLength = pLast - pFirst - 1;
if(newLength > symmeticalLength)
symmeticalLength = newLength;
// Substrings with even length(偶数)
pFirst = pChar;
pLast = pChar + 1;
while( *pLast != '\0' && *pFirst == *pLast)
{
pFirst--;
pLast++;
}
newLength = pLast - pFirst - 1;
if(newLength > symmeticalLength)
symmeticalLength = newLength;
pChar++;
}
return symmeticalLength;
}
int main()
{
cout<<"Please Enter Your String:"<<endl;
char *yourstring = new char[1000];
cin>>yourstring;
cout<<"The Max Symmetrical SubString Length is:"<<endl;
cout<<GetLongestSymmetricalLength_2(yourstring)<<endl;
delete[] yourstring;
system("pause");
return 0;
}
// MaxSymmetricalSubstringLenth.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
/*********************************************************************
* 计算字符串最大对称子串的长度
*********************************************************************/
int GetLongestSymmetricalLength_2(char* pString)
{
if(pString == NULL)
return 0;
int symmeticalLength = 1;
char* pChar = pString;
while(*pChar != '\0')
{
// Substrings with odd length(奇数)
char* pFirst = pChar - 1;
char* pLast = pChar + 1;
while(*pLast != '\0' && *pFirst == *pLast)
{
pFirst--;
pLast++;
}
int newLength = pLast - pFirst - 1;
if(newLength > symmeticalLength)
symmeticalLength = newLength;
// Substrings with even length(偶数)
pFirst = pChar;
pLast = pChar + 1;
while( *pLast != '\0' && *pFirst == *pLast)
{
pFirst--;
pLast++;
}
newLength = pLast - pFirst - 1;
if(newLength > symmeticalLength)
symmeticalLength = newLength;
pChar++;
}
return symmeticalLength;
}
int main()
{
cout<<"Please Enter Your String:"<<endl;
char *yourstring = new char[1000];
cin>>yourstring;
cout<<"The Max Symmetrical SubString Length is:"<<endl;
cout<<GetLongestSymmetricalLength_2(yourstring)<<endl;
delete[] yourstring;
system("pause");
return 0;
}
分享到:
相关推荐
主要介绍了使用C语言提取子字符串及判断对称子字符串最大长度,文后附送了一道ACM竞赛题目,需要的朋友可以参考下
主要介绍了c语言输出字符串中最大对称子串长度的3种解决方案,需要的朋友可以参考下
题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。
由于诸如蛮力之类的方法,诸如字符串长度之类的含义可能是时间复杂度的问题。 D:对于一个解决方案,我希望有良好的时间复杂度,以及一个对每个字符串都有效的好的模式,不管它的长度如何。 E:首先,为了降低时间...
13.3 字符串的所有子回文字符串 13.4 最长公共子序列问题 13.5 字符串的编辑距离 13.6 不同路径之和 13.6.1 无障碍13.6.2 有障碍 13.7 最大矩形面积 13.8 字符串交叉组合 13.9 旋转字符串 13.10 最小路径和 13.11 ...
字符串hash 堆 二维树状数组 Trie树 二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理...
最大子序和 Java 数组、动态规划 58 最后一个单词的长度 Java 字符串 66 加一 Java 数组、数学 67 二进制求和 Java 数学、字符串 69 x 的平方根 Java 数学、二分查找 70 爬楼梯 Java 动态规划 83 删除排序链表中的...
JSpider 联系&交流 微信:scrapingdance 邮箱: 关于 JSpider的含义是JavaScript与Spider,JSpider每周会更新至少一个网站的JS解密方式。并且把解密的JS文件分享...对称性加密一般会按照固定长度,把待加密字符串分
leetcode 信封leetcode 解决方案 1800个最热门的问题leetcode ...具有唯一字符的连接字符串的最大长度118 帕斯卡三角354个俄罗斯娃娃信封第268话第1229章 会议安排642设计检索自动完成系统第545章 二叉树的边界19
1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调递减(或递增)子序列..............121 1.5.9. 四对括号可以有多少种匹配排列方式........
73 <br>0106 如何获得一个字符串中数字的长度 74 <br>0107 如何获得字符串中数字或字母的长度 74 <br>0108 如何获得字符串中某个数字的位置 75 <br>0109 获得字符串中汉字的个数 76 <br>0110...
7.判断一个字符串是否是回文串,忽略大小写与空格 8.遍历二叉树,判断是否有一条路径使得和为目标值 (递归) 返回所有符合规则的路径集合(DFS) 9.手写一个数字的平方(递归) 10.去除一个数组中重复的数字,并返回新...
字符串转换整数 (atoi) 9 回文数 14 最长公共前缀 19 删除链表的倒数第N个节点 20 有效的括号 21 合并两个有序链表 22 括号生成 23 合并K个排序链表 26 删除排序数组中的重复项 27 移除元素 28 实现strStr() 33 搜索...
:copyright:2019 Stuart Edward Schechter(Github:@uppajung)DiceKeys种子加密技术库此c ++库用于支持从种子字符串和以JSON格式指定的一组派生参数(指定密钥的类型,密钥的长度等)生成种子,对称密钥,公共/...
全书分6篇共25章,主要内容有C#开发环境的使用、C#语言基础应用、字符串处理技术、数组和集合的使用、面向对象编程技术、数据结构与算法、Windows窗体基础、特色窗体界面、窗体控制技术、MDI窗体和继承窗体、Windows...