定義
- 特殊的線性表尉间，每個(gè)元素都是字符
- 元素可以是零個(gè)或多個(gè)
常用操作
查找子串砰左、串的相似度、截取勤哗、反轉(zhuǎn)、最長公共子串校摩、分詞稻励、回文
順序?qū)崿F(xiàn)
- 字符串的操作一般都不改變內(nèi)存空間（例外：連接兩個(gè)字符串），因此順序存儲整體效率更高
- 存儲單元大卸耪＝串真實(shí)長度＋1（"\0"占一個(gè)字節(jié)空間）
- 比較適合的操作：查找、截取
鏈?zhǔn)酱鎯?/em>
- 類似插入算途、刪除的操作是效率較高的塞耕，截取就不好了
經(jīng)典算法
樸素的模式匹配算法
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/simpleChuan.png
代碼實(shí)現(xiàn)：
#include <stdio.h>
int main(int args,char *argv[])
{
char S[] = "abcde";
char T[4] = "cde";
int slen = sizeof(S);
int tlen = sizeof(T);
int i = 0;
int j = 0;
int from = 0;
while(i<slen && j<tlen)
{
if(S[i]==T[j])
{
from = (from==0)?i:from;
i++;
j++;
}else
{
i = i-j+1;
j = 0;
from = 0;
}
}
if(j==tlen)
{
printf("include subString from index %d\n",from);
}else
{
printf("no match!!\n");
}
return 0;
}
- while(i<slen && j<tlen)是降低時(shí)間復(fù)雜度的關(guān)鍵（相對于雙層循環(huán)）
KMP算法
