先來看一個使用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; }
判斷回文子串
判斷子串是否為回文，可以考慮從內向外比較。例如字符串“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
****************************************************************/
新聞熱點
疑難解答
圖片精選
