先来看一个使用C语言从字符串中提取子字符串的基本方法总结：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
#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;} |
判断对称子字符串最大长度的方法
判断回文
先重写一个判断回文字串的方法，用指针实现，而不是数组了
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#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
****************************************************************/
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代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#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
****************************************************************/
