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

   2015-08-12 0
核心提示:这篇文章主要介绍了使用C语言提取子字符串及判断对称子字符串最大长度,文后附送了一道ACM竞赛题目,需要的朋友可以参考下

先来看一个使用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
    ****************************************************************/ 

 
标签: C 子字符串
反对 0举报 0 评论 0
 

免责声明:本文仅代表作者个人观点,与乐学笔记(本网)无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
    本网站有部分内容均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责,若因作品内容、知识产权、版权和其他问题,请及时提供相关证明等材料并与我们留言联系,本网站将在规定时间内给予删除等相关处理.

  • 拓端tecdat|R语言VAR模型的不同类型的脉冲响应
    原文链接:http://tecdat.cn/?p=9384目录模型与数据估算值预测误差脉冲响应识别问题正交脉冲响应结构脉冲反应广义脉冲响应参考文献脉冲响应分析是采用向量自回归模型的计量经济学分析中的重要一步。它们的主要目的是描述模型变量对一个或多个变量的冲击的演化
    03-16
  • 《黑马程序员》 category分类的使用(Objective
    分类的作用:在不改变原来类的基础上,可以给类增加一些方法。使用注意 : ①  分类只能增加方法,不可以增加成员变量                ②  分类的方法在实现中可以访问成员变量,不过成员变量必须手动实现。               
    03-16
  • Windows API Reference for C#, VB.NET
    不错的.net 下用API的参考站点地址在:http://www.webtropy.com/articles/Win32-API-DllImport-art9.asp 下面摘抄分类,便于大家直接就拿来用: File, Memory, Process, Threading, Time, Console, and Comm control(kernel32.dll) _hread_hwrite_lclose_lcr
    03-16
  • 拓端tecdat|R语言代写实现向量自回归VAR模型
    原文链接:http://tecdat.cn/?p=8478 澳大利亚在2008 - 2009年全球金融危机期间发生了这种情况。澳大利亚政府发布了一揽子刺激计划,其中包括2008年12月的现金支付,恰逢圣诞节支出。因此,零售商报告销售强劲,经济受到刺激。因此,收入增加了。VAR面临的批
    03-16
  • 项目中使用TypeScript的TodoList实例详解
    项目中使用TypeScript的TodoList实例详解
    目录为什么用todolisttodolist的ts化数据到视图实现handleTodoItemreadonly分类交叉类型新增功能联合类型可选属性数据转视图总结为什么用todolist现代的框架教程目前再也不是写个hello world那么简单了,而是需要有一定基础能力能够做到数据绑定、遍历、条件
    03-16
  • 我只是想在我的 Mac 上将 Ruby 和 Rails 更新到终端中的最新版本。 .
    我只是想在我的 Mac 上将 Ruby 和 Rails 更新到
    介绍自从我尝试创建一个简单的应用程序以来已经有很长时间了,并且我尝试在创建它之前将 Ruby 和 Rails 更新到最新版本,但是我意外卡住了,所以我将它作为备忘录留下。作为版本升级1. 更新 Homebrew 和 rbenv2. 红宝石更新3. Rails 更新这就是它的感觉。让我
    03-16
  • Objective-C学习—UIScrollView控件使用
    Objective-C学习—UIScrollView控件使用
    一、知识点简单介绍1.UIScrollView控件是什么?(1)移动设备的屏幕⼤大⼩小是极其有限的,因此直接展⽰示在⽤用户眼前的内容也相当有限(2)当展⽰示的内容较多,超出⼀一个屏幕时,⽤用户可通过滚动⼿手势来查看屏幕以外的内容(3)普通的UIView不具备滚动功能
    03-16
  • SICP:复数的直角和极坐标的表示(Python实现)
    SICP:复数的直角和极坐标的表示(Python实现)
    数据抽象屏障是控制复杂性的强有力工具,然而这种类型的数据抽象还不够强大有力。从一个另一个角度看,对于一个数据对象可能存在多种有用的表示方式,且我们希望所设计的系统能够处理多种表示形式。比如,复数就可以表示为两种几乎等价的形式:直角坐标形式(
    03-16
  • 微信小程序中overflow:scroll失效的问题 微信小程序overflow设置滚动
    微信小程序中overflow:scroll失效的问题 微信小
    .common-pop-table {padding: 0 30rpx;overflow: scroll;max-height: 70%;}研究后发现,要实际的设置对应的那个维度的高度,wcss改成.common-pop-table {padding: 0 30rpx;overflow: scroll;max-height: 400px;}就恢复正常了
    03-08
  • bloom-server 基于 rust 编写的 rest api cache 中间件
    bloom-server 基于 rust 编写的 rest api cache
    bloom-server 基于 rust 编写的 rest api cache 中间件,他位于lb 与api worker 之间,使用redis 作为缓存内容存储, 我们需要做的就是配置proxy,同时他使用基于share 的概念,进行cache 的分布存储,包含了请求端口(proxy,访问数据) 以及cache 控制端口(
    03-08
点击排行