首页 > 编程 > C > 正文

使用C语言提取子字符串及判断对称子字符串最大长度

2020-01-26 14:59:03
字体:
来源:转载
供稿:网友

先来看一个使用C语言从字符串中提取子字符串的基本方法总结:

#include <stdio.h>/*处理中文字符*//*遍历字符串,非ASCII字符读取2个字节,ASCII读取一个字节,获取字符串长度*/int StrLenU(const char* string){   int len = 0 ;   const char* p = string;   while(*p++ != '/0')   {     if(*p > 0x80 || *p < 0)     {      p++;     }     len++;   }   return len;}/*遍历字符串,非ASCII字符读取2个字节,ASCII读取一个字节,返回指定位置的字符串指针,默认从1开始*/char* StrSetPosU(const char* string,int pos){   char* result;   result = string;   while (result != NULL && *result != '/0' && pos > 1)   {     if(*result > 0x80 || *result < 0)     {       result++;     }     result++;     pos--;   }   if(pos!=0)     return result;   return '/0';}/*获取指定内存中的字符串个数,中文字符作为一个字符*/int StrLenMemU(const char* string,int size){     int len = 0 ;   const char* p = string;   while(*p++ != '/0' && size > 0)   {     if(*p > 0x80 || *p < 0)     {      p++;      size--;      }     size-- ;     len++;   }   return len;}/*可取中文字符串,当number为-1等负数时,取从start开始的剩余所有字符,默认从1开始*/char* StringSubU(const char* string,int start,int number){   int len = StrLenU(string) ;   if(start>len)   {     printf("Start %d is too big than string length %d!/n",start,len);     return NULL;   }   int bufsize = 0;   int num = number;   const char* p = string;   const char* 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 : %d is to big!/n",number);        break;      }      /*当num为0时,说明读取字符已经满足要求*/      else if(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));   /*开始复制字符串*/   int i = 0;   int j = 0;   while(num != 0)   {     result[i++] = start_char[j++];     num--;   }   /*尾部置零*/   result[bufsize] = '/0';   return result;}int main(){   /*进行测试*/   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));   return 0;}

判断对称子字符串最大长度的方法

判断回文
先重写一个判断回文字串的方法,用指针实现,而不是数组了

  #include <stdio.h>   #include <stdlib.h>   #include <string.h>       void isSymmetrical(char *str)   {     char *begin, *end;     int flag, 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");   }           int main(void)   {     char str[1001];         while (gets(str)) {       isSymmetrical(str);     }         return 0;   }       
/**************************************************************
        Problem: 1192
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:10 ms
        Memory:912 kb
    ****************************************************************/ 


判断回文子串
判断子串是否为回文,可以考虑从内向外比较。例如字符串“google”,如果我们判断第二个字符o是对称的,只需要再向左、和向右各移一位就可以判断下一个字符串是否是对称的了
需要注意的一点是,针对原字符串中的每一个字符有两种情况:

    以该字符为中心的对称分布,也就是回文子串为奇数
    以该字符和该字符前一个字符为中心的对称分布,也就是说回文子串是偶数


时间复杂度分析:

外层需要n - 1层循环,内层对于每个字符,都由中间向两边遍历一遍,为n,因此总的时间复杂度为O(n * n)

题目

    题目描述: 
    输入一个字符串,输出该字符串中对称的子字符串的最大长度。 
    比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。 
    输入: 
    存在多组数据,每组数据一行字符串,长度不大于100。 
    输出: 
    输出回文子串的最大长度。 
    样例输入: 
    google 
    样例输出: 
    4 


ac代码

 

  #include <stdio.h>   #include <string.h>   #include <stdlib.h>       /**    * 最长回文字串的长度    */   void maxSymmetricalSubstring(char *str)   {     int maxlength, 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);   }         int main(void)   {     char str[101];         while (gets(str)) {       maxSymmetricalSubstring(str);     }         return 0;   } 

    /**************************************************************
        Problem: 1252
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:0 ms
        Memory:912 kb
    ****************************************************************/ 

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表

图片精选