第一篇鏈接：字符串類習題、面試題詳解（第一篇）
6題：回文串（競賽基礎題）
輸入一個字符串，求出其最長回文子串。子串的含義是：在原串中連續出現的字符串片段。回文的含義是：正著看和倒著看相同，如abba和yyxyy。在判斷時，應該忽略所有標點符號和空格，且忽略大小寫，但輸出應保持原樣（在回文串的首部和尾部不要輸出多余字符）。輸入字符串長度不超過5000，且占據單獨一行。應該輸出最長的回文串，如果有多個，輸出起始位置最靠左的。
樣例輸入：Confuciuss say: Madam, I’m Adam.
樣例輸出：Madam,I’m Adam
方法1：枚舉回文串的起點和終點。
1 #include <stdio.h>
2 #include <ctype.h>
3 #include <string.h>
4 #define MAXN 5000 + 10
5
6 char buf[MAXN], s[MAXN];
7 int p[MAXN];
8
9 int main(void)
10 {
11 int n, m = 0, max = 0, x = 0, y = 0;
12 int i, j, k, ok;
13 fgets(buf, sizeof(buf), stdin);
14 n = strlen(buf);
15
16 for (i = 0; i < n; i++)
17 {
18 if (isalpha(buf[i]))
19 {
20 p[m] = i; //保存字符的實際位置
21 s[m++] = toupper(buf[i]); //保存為大寫字母
22 }
23 }
24
25 for (i = 0; i < m; i++) //枚舉回文串起始位置
26 {
27 for (j = i; j < m; j++) //枚舉回文串終止位置
28 {
29 ok = 1;
30 for (k = i; k <= j; k++)
31 {
32 if (s[k] != s[i + j - k])
33 ok = 0;
34 }
35
36 if (ok && j - i + 1 > max)
37 {
38 max = j - i + 1;
39 x = p[i];
40 y = p[j];
41 }
42 }
43 }
44
45 for (i = x; i <= y; i++)
46 {
47 printf("%c", buf[i]);
48 }
49 printf("\n");
50
51 return 0;
52 }
方法2：枚舉回文串的中間位置。
1 #include <stdio.h>
2 #include <string.h>
3 #include <ctype.h>
4 #define MAXN 5000 + 10
5 char buf[MAXN], s[MAXN];
6 int p[MAXN];
7
8 int main(void)
9 {
10 int n, m = 0, max = 0, x = 0, y = 0;
11 int i, j;
12 fgets(buf, sizeof(buf), stdin);
13 n = strlen(buf);
14
15 for (i = 0; i < n; i++)
16 {
17 if (isalpha(buf[i]))
18 {
19 p[m] = i; //保存字符實際位置
20 s[m++] = toupper(buf[i]);
21 }
22 }
23
24 for (i = 0; i < m; i++) //枚舉回文串的中間位置
25 {
26 for (j = 0; i - j >= 0 && i + j < m; j++) //回文子串長度為奇數
27 {
28 if (s[i - j] != s[i + j])
29 break;
30 if (j * 2 + 1 > max)
31 {
32 max = j * 2 + 1;
33 x = p[i - j];
34 y = p[i + j];
35 }
36 }
37
38 for (j = 0; i - j >= 0 && i + j + 1 < m; j++) //回文串長度為偶數
39 {
40 if (s[i - j] != s[i + j + 1])
41 break;
42 if (j * 2 + 2 > max)
43 {
44 max = j * 2 + 2;
45 x = p[i - j];
46 y = p[i + j + 1];
47 }
48 }
49 }
50
51 for (i = x; i <= y; i++)
52 printf("%c", buf[i]);
53 printf("\n");
54
55 return 0;
56 }
解析：枚舉回文串的中間位置時要注意長度為奇數和偶數的處理方式是不一樣的。
7題：編碼實現求給定字符串(全為小寫英文字母)的最小後繼，如"abc"的最小後繼為"abd"，"dhz"的最小後繼為"di"。（Google筆試題）
1 #include <stdio.h>
2 #include <string.h>
3 #define MAXN 1024
4
5 int main(void)
6 {
7 char buf[MAXN];
8 int n, m, i;
9 scanf("%s", buf);
10
11 n = strlen(buf);
12 for (i = n - 1; i >= 0; i--)
13 {
14 if (buf[i] + 1 <= 'z')
15 {
16 buf[i] += 1;
17 buf[i + 1] = '\0';
18 break;
19 }
20 }
21 printf("%s\n", buf);
22
23 return 0;
24 }
解析：對最後一個字符+1，如果大於'z'則對前一個字符+1，如果又大於 'z' 則重復之前的步驟。
8題：X86結構下，下面代碼的printf輸出結果是什麼？（西艾面試題）
1 #include <stdio.h>
2
3 int main(void)
4 {
5 char str[20]="Good night";
6 int *p = (int *)str;
7 p[0] = 0x61626364;
8 p[1] = 0x31323334;
9 p[2] = 0x41424344;
10 printf("%s\n", str);
11
12 return 0;
13 }
解析：輸出結果為：dcba4321DCBA。X86結構下，數據的低位保存在內存的低地址中，數據的高位保存在內存的高地址中。還需要注意常見字符的ASCII碼（十進制），’a’為97，’A’為65，’1’為49。
9題：編一個函數，輸入一個字符串，要求做一個新字符串，把其中所有的一個或多個連續的空白字符都壓縮為一個空格。這裡所說的空白包括空格、'\t'、'\n'、'\r'。例如原來的字符串是：
This Content hoho is ok
ok?
file system
uttered words ok ok ?
end.
壓縮了空白之後就是：
This Content hoho is ok ok? file systemuttered words ok ok ? end.（面試題）
參考程序如下：
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4
5 const char *p = "This Content hoho is ok\
6 ok?\
7 \
8 file system\n\
9 uttered words ok ok ?\
10 end.";
11
12 int IsSpace(char c)
13 {
14 if (c == ' ')
15 return 1;
16 else if (c == '\n' || c == '\r')
17 return 2;
18 else if (c == '\t')
19 return 3;
20 else
21 return 0;
22 }
23
24 char *shrink_space(char *dest, const char *src, size_t n)
25 {
26 char *t_dest = dest;
27 char temp;
28 int pre = -1, cur = -1, key = -1;
29 while (IsSpace(*src)) //忽略字符串起始空格
30 src++;
31 *t_dest = *src;
32
33 while ((temp = *src++) != '\0')
34 {
35 key = IsSpace(temp);
36 if (0 == key) //0表示字符
37 {
38 cur = 0;
39 *t_dest++ = temp;
40 }
41 else if (1 == key) //1表示空格
42 {
43 if (pre == 1) //如果前面也是空格
44 continue;
45 else
46 {
47 cur = 1;
48 *t_dest++ = temp;
49 }
50 }
51 else if (2 == key && pre == 0)
52 {
53 *t_dest++ = ' ';
54 }
55 else if (3 == key)
56 {
57 if (pre == 1)
58 continue;
59 else
60 {
61 *t_dest++ = ' '; //將\t轉換為1個空格
62 cur = 1;
63 }
64 }
65 pre = cur;
66 }
67 *t_dest = '\0';
68
69 return dest;
70 }
71 int main(void)
72 {
73 int len = strlen(p);
74 char *dest = (char *)malloc(sizeof(char) * (len + 1));
75 shrink_space(dest, p, 1);
76 printf("%s\n", dest);
77 free(dest);
78 dest = NULL;
79
80 return 0;
81 }
10題：寫出在母串中查找子串出現次數的代碼。（面試題）
1 #include <stdio.h>
2 #include <string.h>
3 #define BUFSIZE 1024
4
5 int StrCount(char *strLong, char *strShort)
6 {
7 int result = 0;
8 char *t_strS = strShort;
9 char *t_strD = strLong;
10 while (*t_strD != '\0')
11 {
12 t_strS = strShort; //子串
13 while (*t_strD == *t_strS && *t_strS != '\0' && *t_strD != '\0')
14 {
15 t_strD++;
16 t_strS++;
17 }
18 if (*t_strS == '\0')
19 result += 1;
20 else if (*t_strD == '\0')
21 break;
22 else
23 t_strD++;
24 }
25
26 return result;
27 }
28
29 int main(void)
30 {
31 int len;
32 char strD[BUFSIZE], strS[BUFSIZE];
33 fgets(strD, sizeof(strD), stdin);
34 len = strlen(strD);
35 strD[len - 1] = '\0';
36 fgets(strS, sizeof(strS), stdin);
37 len = strlen(strS);
38 strS[len - 1] = '\0';
39 printf("%d\n", StrCount(strD, strS));
40 return 0;
41 }
