使用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
****************************************************************/