使用C語(yǔ)言提取子字符串及判斷對(duì)稱子字符串最大長(zhǎng)度
先來看一個(gè)使用C語(yǔ)言從字符串中提取子字符串的基本方法總結(jié):
#include <stdio.h>
/*處理中文字符*/
/*遍歷字符串,非ASCII字符讀取2個(gè)字節(jié),ASCII讀取一個(gè)字節(jié),獲取字符串長(zhǎng)度*/
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個(gè)字節(jié),ASCII讀取一個(gè)字節(jié),返回指定位置的字符串指針,默認(rèn)從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';
}
/*獲取指定內(nèi)存中的字符串個(gè)數(shù),中文字符作為一個(gè)字符*/
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;
}
/*可取中文字符串,當(dāng)number為-1等負(fù)數(shù)時(shí),取從start開始的剩余所有字符,默認(rèn)從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;
/*當(dāng)取值為負(fù)值時(shí),則取全部值*/
if(number < 0)
{
while(*p != '\0')
{
p++;
bufsize++;
}
}
else
{
while(1)
{
/*當(dāng)指針移到末尾,而且還沒有獲取指定數(shù)的字符時(shí),說明此時(shí)指定字符數(shù)過多,將會(huì)取剩下的所有值*/
if(*p == '\0' && num > 0)
{
printf("Number : %d is to big!\n",number);
break;
}
/*當(dāng)num為0時(shí),說明讀取字符已經(jīng)滿足要求*/
else if(num ==0 )
break;
/*當(dāng)字符為ASCII時(shí),*/
if(*p > 0x80 || *p < 0)
{
bufsize++;
p++;
}
bufsize++;
p++;
num--;
}
}
num = bufsize;
/*開始分配內(nèi)存*/
char* result ;
result = (char*)malloc(sizeof(char)*(bufsize+1));
memset(result,0,sizeof(char)*(bufsize+1));
/*開始復(fù)制字符串*/
int i = 0;
int j = 0;
while(num != 0)
{
result[i++] = start_char[j++];
num--;
}
/*尾部置零*/
result[bufsize] = '\0';
return result;
}
int main()
{
/*進(jìn)行測(cè)試*/
char* t = "a哈哈aab和c哈";
printf("length: %d\n",StrLenU("哈哈a哈a哈"));
printf("指向前%s\n指向后:%s\n",t,StrSetPosU(t,3));
printf("全字符時(shí)字符個(gè)數(shù):%d\n",StrLenMemU(t,6));
printf("半個(gè)字符時(shí)字符個(gè)數(shù):%d\n",StrLenMemU(t,4));
printf("1.正常取值:%s\n",StringSubU("a哈aa哈a",1,2));
printf("2.負(fù)值取值:%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.負(fù)值取全部:%s\n",StringSubU("a哈aa哈a",4,-1));
return 0;
}
判斷對(duì)稱子字符串最大長(zhǎng)度的方法
判斷回文
先重寫一個(gè)判斷回文字串的方法,用指針實(shí)現(xiàn),而不是數(shù)組了
#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
****************************************************************/
判斷回文子串
判斷子串是否為回文,可以考慮從內(nèi)向外比較。例如字符串“google”,如果我們判斷第二個(gè)字符o是對(duì)稱的,只需要再向左、和向右各移一位就可以判斷下一個(gè)字符串是否是對(duì)稱的了
需要注意的一點(diǎn)是,針對(duì)原字符串中的每一個(gè)字符有兩種情況:
以該字符為中心的對(duì)稱分布,也就是回文子串為奇數(shù)
以該字符和該字符前一個(gè)字符為中心的對(duì)稱分布,也就是說回文子串是偶數(shù)
時(shí)間復(fù)雜度分析:
外層需要n - 1層循環(huán),內(nèi)層對(duì)于每個(gè)字符,都由中間向兩邊遍歷一遍,為n,因此總的時(shí)間復(fù)雜度為O(n * n)
題目
題目描述:
輸入一個(gè)字符串,輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。
比如輸入字符串“google”,由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”,因此輸出4。
輸入:
存在多組數(shù)據(jù),每組數(shù)據(jù)一行字符串,長(zhǎng)度不大于100。
輸出:
輸出回文子串的最大長(zhǎng)度。
樣例輸入:
google
樣例輸出:
4
ac代碼
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/**
* 最長(zhǎng)回文字串的長(zhǎng)度
*/
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
****************************************************************/
相關(guān)文章
動(dòng)態(tài)數(shù)組C++實(shí)現(xiàn)方法(分享)
下面小編就為大家?guī)硪黄獎(jiǎng)討B(tài)數(shù)組C++實(shí)現(xiàn)方法(分享)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-05-05
C++實(shí)現(xiàn)LeetCode(123.買股票的最佳時(shí)間之三)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(123.買股票的最佳時(shí)間之三),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言實(shí)現(xiàn)的雙鏈表功能完整示例
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)的雙鏈表功能,結(jié)合完整實(shí)例形式分析了基于C語(yǔ)言實(shí)現(xiàn)的雙鏈表定義、添加、刪除、排序等相關(guān)操作實(shí)現(xiàn)技巧,需要的朋友可以參考下2018-04-04
Linux中使用C語(yǔ)言的fork()函數(shù)創(chuàng)建子進(jìn)程的實(shí)例教程
fork是一個(gè)在Linux系統(tǒng)環(huán)境下專有的函數(shù),現(xiàn)有的進(jìn)程調(diào)用fork后將會(huì)創(chuàng)建一個(gè)新的進(jìn)程,這里我們就來看一下Linux中使用C語(yǔ)言的fork()函數(shù)創(chuàng)建子進(jìn)程的實(shí)例教程2016-06-06
C++實(shí)現(xiàn)簡(jiǎn)單的HTTP服務(wù)器
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單的HTTP服務(wù)器的相關(guān)資料,感興趣的朋友可以參考下2016-05-05

