使用C语言提取子字符串及判断对称子字符串最大长度
先来看一个使用C语言从字符串中提取子字符串的基本方法总结：
#include<stdio.h>
/*处理中文字符*/
/*遍历字符串，非ASCII字符读取2个字节，ASCII读取一个字节，获取字符串长度*/
intStrLenU(constchar*string)
{
intlen=0;
constchar*p=string;
while(*p++!='\0')
{
if(*p>0x80||*p<0)
{
p++;
}
len++;
}
returnlen;
}
/*遍历字符串，非ASCII字符读取2个字节，ASCII读取一个字节，返回指定位置的字符串指针，默认从1开始*/
char*StrSetPosU(constchar*string,intpos)
{
char*result;
result=string;
while(result!=NULL&&*result!='\0'&&pos>1)
{
if(*result>0x80||*result<0)
{
result++;
}
result++;
pos--;
}
if(pos!=0)
returnresult;
return'\0';
}
/*获取指定内存中的字符串个数，中文字符作为一个字符*/
intStrLenMemU(constchar*string,intsize)
{
intlen=0;
constchar*p=string;
while(*p++!='\0'&&size>0)
{
if(*p>0x80||*p<0)
{
p++;
size--;
}
size--;
len++;
}
returnlen;
}
/*可取中文字符串，当number为-1等负数时，取从start开始的剩余所有字符，默认从1开始*/
char*StringSubU(constchar*string,intstart,intnumber)
{
intlen=StrLenU(string);
if(start>len)
{
printf("Start%distoobigthanstringlength%d!\n",start,len);
returnNULL;
}
intbufsize=0;
intnum=number;
constchar*p=string;
constchar*start_char=string;
/*重置指针，获取指定开始位置*/
p=StrSetPosU(string,start);
start_char=p;
/*当取值为负值时，则取全部值*/
if(number<0)
{
while(*p!='\0')
{
p++;
bufsize++;
}
}
else
{
while(1)
{
/*当指针移到末尾，而且还没有获取指定数的字符时，说明此时指定字符数过多，将会取剩下的所有值*/
if(*p=='\0'&&num>0)
{
printf("Number:%distobig!\n",number);
break;
}
/*当num为0时，说明读取字符已经满足要求*/
elseif(num==0)
break;
/*当字符为ASCII时，*/
if(*p>0x80||*p<0)
{
bufsize++;
p++;
}
bufsize++;
p++;
num--;
}
}
num=bufsize;
/*开始分配内存*/
char*result;
result=(char*)malloc(sizeof(char)*(bufsize+1));
memset(result,0,sizeof(char)*(bufsize+1));
/*开始复制字符串*/
inti=0;
intj=0;
while(num!=0)
{
result[i++]=start_char[j++];
num--;
}
/*尾部置零*/
result[bufsize]='\0';
returnresult;
}
intmain()
{
/*进行测试*/
char*t="a哈哈aab和c哈";
printf("length:%d\n",StrLenU("哈哈a哈a哈"));
printf("指向前%s\n指向后:%s\n",t,StrSetPosU(t,3));
printf("全字符时字符个数:%d\n",StrLenMemU(t,6));
printf("半个字符时字符个数:%d\n",StrLenMemU(t,4));
printf("1.正常取值:%s\n",StringSubU("a哈aa哈a",1,2));
printf("2.负值取值:%s\n",StringSubU("a哈aa哈a",-1,2));
printf("3.起始值过大:%s\n",StringSubU("a哈aa哈a",7,2));
printf("4.取值过大:%s\n",StringSubU("a哈aa哈a",5,3));
printf("5.负值取全部:%s\n",StringSubU("a哈aa哈a",4,-1));
return0;
}
判断对称子字符串最大长度的方法
判断回文
先重写一个判断回文字串的方法，用指针实现，而不是数组了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
voidisSymmetrical(char*str)
{
char*begin,*end;
intflag,len=strlen(str);
for(begin=str,end=str+len-1,flag=1;begin<=end;begin++,end--){
if(*begin!=*end){
flag=0;
break;
}
}
if(flag)
printf("Yes!\n");
else
printf("No!\n");
}
intmain(void)
{
charstr[1001];
while(gets(str)){
isSymmetrical(str);
}
return0;
}
Problem:1192
User:wangzhengyi
Language:C
Result:Accepted
Time:10ms
Memory:912kb
****************************************************************/
判断回文子串
判断子串是否为回文，可以考虑从内向外比较。例如字符串“google”，如果我们判断第二个字符o是对称的，只需要再向左、和向右各移一位就可以判断下一个字符串是否是对称的了
需要注意的一点是，针对原字符串中的每一个字符有两种情况：
以该字符为中心的对称分布，也就是回文子串为奇数
以该字符和该字符前一个字符为中心的对称分布，也就是说回文子串是偶数
时间复杂度分析：
外层需要n-1层循环，内层对于每个字符，都由中间向两边遍历一遍，为n，因此总的时间复杂度为O（n*n）
题目
题目描述：
输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
输入：
存在多组数据，每组数据一行字符串，长度不大于100。
输出：
输出回文子串的最大长度。
样例输入：
google
样例输出：
4
ac代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/**
*最长回文字串的长度
*/
voidmaxSymmetricalSubstring(char*str)
{
intmaxlength,len;
char*pre,*next,*current;
current=str+1;
maxlength=0;
while(*current!='\0'){
pre=current-1;
next=current+1;
while(pre>=str&&*next!='\0'&&*pre==*next){
pre--;
next++;
}
len=(next-1)-(pre+1)+1;
if(len>maxlength){
maxlength=len;
}
pre=current-1;
next=current;
while(pre>=str&&*next!='\0'&&*pre==*next){
pre--;
next++;
}
len=(next-1)-(pre+1)+1;
if(len>maxlength){
maxlength=len;
}
current++;
}
printf("%d\n",maxlength);
}
intmain(void)
{
charstr[101];
while(gets(str)){
maxSymmetricalSubstring(str);
}
return0;
}
/**************************************************************
Problem:1252
User:wangzhengyi
Language:C
Result:Accepted
Time:0ms
Memory:912kb
****************************************************************/