本次講課講全面介紹字元串以及如何使用字元串解決具體問題。
一、什麼是字元串
1.如何存儲字元串
平時我們使用的變量有很多，int代表整型變量，double代表浮點型變量，char代表字元型變量，那麼對于一個字元串例如“Hello World!”應該如何存儲并操作呢。
在C語言裡，我們可以char數組進行存儲，例如：
1 char str1[] = "Hello World!";
2 char* str2 = "Hello World!";
3 char str3[20] = "Hello World!"; 對str1、2、3進行輸出都為“Hello World!”，這三種方式構造一個字元串的差別有哪些？我們輸出他們的空間長度（注意是占用的空間長度而不是字元串長度）。
1 int len1 = sizeof(str1)/sizeof(char);
2 int len2 = sizeof(str2)/sizeof(char);
3 int len3 = sizeof(str3)/sizeof(char);
4 printf("%d\n%d\n%d\n",len1,len2,len3);
結果為：13
4
20 （此處應對上訴結果進行解釋說明 ==）
既然字元串可以存儲在一個字元數組裡面，那麼如何對字元串進行操作想必也就非常清楚了。需要注意的是，對于計算機可以字元和一個整型變量沒有任何差別，它們都是資料，是以對整型變量可以做的操作都可以對一個字元進行同樣的操作。
2.ASCII編碼
衆所周知字元在C/C++裡面是以ASCII碼的形式存儲在計算機中，既然字元串是存儲在字元數組裡面的，其實也就是多個字元的一個有序集合。它也遵守和字元同樣的的規則，例如'A'的ASCII碼為65，如果我們進行下列語句
1 char ch = 'A';
2 if(ch == 'A'){
3 ch = ch + 5;
4 }
5 else {
6 ch = ch - 1;
7 } 那麼這裡ch的值應該變成多少了呢？此時的ch又代表哪個字元呢？
3.std::string
是不是沒見過這是什麼東西，它其實就是character string（字元串），這是一個C++的語句，意思就是調用std（标準命名空間）裡面的string類，可能你也已經猜到了string是用來幹什麼的，是的它可以直接定義一個字元串變量，并且能夠直接對串進行操作。
什麼意思呢？我們既然已經能夠用字元數組存儲字元串了，為什麼還需要多個string呢，因為我們前面說了字元串數組相當于一個字元的有序集合，歸根到底還都是單個字元，而字元串變量string才是真正的字元串，它可以直接對串操作，例如下列語句：
std::string str = "Hello";
str += " World";
str += "!"; 如果僅僅隻是這樣，那麼string并不顯得強大，事實上string支援下面的功能
我是傳送門：string的用法但是值得注意的是，string是c++語言的東西，在c語言中并不能使用，而且string隻能通過cin流進行讀入操作，同樣可以使用下标對string字元串進行每一位的通路以及操作。
C++也還有很多C語言沒有的容器，通過這些容器對做題有很大幫助，而且這些容器對于一個ACMer來說是必須要掌握的，詳情請戳：
STL容器（Stack, Queue, List, Vector, Deque, Priority_Queue, Map, Pair, Set, Multiset, Multimap）二、字元串操作
1.空格、換行符
我們知道使用scanf("%s",s);讀入一個字元串遇到空格和換行符自動跳出，但是對于一個字元串不可能都沒有空格以及換行呀，如果是需要讀入一個句子那該怎麼辦呢，對于C語言，我提供了下列幾種方法供參考
1 //方法一——判斷是否為空格選擇繼續讀入還是跳出
2 char s[100],ch;
3 scanf("%s",s);
4 ch = getchar();
5 while(ch == ' '){
6 int len = strlen(s);
7 s[len] = ' ';
8 scanf("%s",s+len+1);
9 ch = getchar();
10 }
11
12 //方法二——利用格式符%[]設定結束符
13 char s[100];
14 scanf("%[^\n]",s);
15
16
17 //方法三——利用不安全的gets進行讀入
18 char s[100];
19 gets(s); 三種方法都可以進行讀入以換行符為結束符帶有空格的字元串，但是我推薦最好使用第一種，為什麼？
（此處應對上述進行解釋說明）
在C++語言中，想要讀入這樣的串，我也同樣提供幾種方法供參考
1 //方法一——使用cin流對字元串進行讀入
2 char s[100];
3 cin.getline(s,100);
4
5 //方法二——使用getline進行string類讀入
6 string s;
7 getline(cin,s); 下面以一個例題為例，對字元串的具體操作進行講解
題目連結：
http://120.78.128.11/Problem.jsp?pid=1716下面我貼出C語言和C++語言的代碼
C語言：
1 #include <stdio.h>
2 #include <string.h>
3 char s1[10005],s2[105];
4
5 void read(char *s){
6 int ch;
7 scanf("%s",s);
8 ch = getchar();
9 while(ch == ' '){
10 int len = strlen(s);
11 s[len] = ' ';
12 scanf("%s",s+len+1);
13 ch = getchar();
14 }
15 }
16
17 int main(){
18 int t;
19 scanf("%d",&t);
20 while(t--){
21 read(s1),read(s2);//讀入字元串
22 int len1 = strlen(s1),len2 = strlen(s2);
23 int flag = -1,i,j;
24 for(i = 0; i < len1; i++){
25 if(s1[i] == s2[0]){
26 for(j = 0; j < len2; j++){
27 if(j == len2-1 && s1[i+j] == s2[j])
28 flag = i+1;
29 if(s1[i+j] != s2[j])
30 break;
31 }
32 }
33 }
34 printf("%d\n",flag);
35 }
36 return 0;
37 } C++語言：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 string s1,s2;
5
6 int main(){
7 int t;
8 cin>>t;
9 cin.get();
10 while(t--){
11 getline(cin,s1),getline(cin,s2);
12 int pos = s1.find(s2);
13 cout << (pos==-1?-1:pos+1) << endl;
14 }
15 return 0;
16 } 這也是為什麼要用C++的原因，C++内置函數以及操作實在是太強大了，兩個C中較為冗長的函數在C++中都隻要用一句便實作了。
另一個例題：
http://120.78.128.11/Problem.jsp?pid=1924C語言代碼：
1 #include <stdio.h>
2 #include <string.h>
3 char s[1000005];
4
5 void read(char *s){
6 int ch;
7 scanf("%s",s);
8 ch = getchar();
9 while(ch == ' '){
10 int len = strlen(s);
11 s[len] = ' ';
12 scanf("%s",s+len+1);
13 ch = getchar();
14 }
15 }
16
17 int main(){
18 int t,i;
19 scanf("%d",&t);
20 while(t--){
21 read(s);
22 int len = strlen(s);
23 for(i = 0; i < len; i++){
24 if(i == 0){
25 putchar(s[i]-32);
26 }
27 if(s[i] == ' '){
28 putchar(s[i+1]-32);
29 }
30 }
31 puts("");
32 }
33 return 0;
34 } C++代碼：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 string s;
5
6 int main(){
7 int t;
8 cin>>t;
9 cin.get();
10 while(t--){
11 getline(cin,s);
12 int len = s.size();
13 cout << char(s[0]-32);
14 for(int i = 1; i < len; i++){
15 if(s[i] == ' ')
16 cout << char(s[i+1]-32);
17 }
18 cout << endl;
19 }
20 return 0;
21 } 2.字元串比較
我們知道可以通過一位一位的模拟進行字元串比較，但要是兩個字元串都很長怎麼辦，我們容易得出暴力方法進行比對的時間複雜度為O(n*m)，n和m就是兩個字元串的長度，通過一些算法我們可以進行比對優化，例如我們可以利用KMP算法在O(n+m)的時間複雜度内進行比對。
下面是KMP的算法講解
我是傳送門：KMP算法 傳送門：KMP例題![[轉]九大排序算法——C語言實作及詳解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)