1、串：由零個或多個字符組成的有限序列，記作S='a1a2a3...an'(n>=0)，其中，S為串名，單引號括起來的字符序列為串的值，
1）串中字符的個數n為串的長度，n=0時的串稱為空串，
2）串相等：兩個串的長度相等且每個對應位置的字符都相等，
3）空格串：由一個或多個空格組成的串，其長度為串中空格字符的個數，
2、串的存盤結構
1）定長順序存盤
（1）截斷：超過預定義長度的串值被舍去，
（2）串長的表示方法：用額外的變數存盤串的長度、在串值后面加上不計入串長的標記符號“\0”，
（3）定長順序存盤結構描述
#define maxlen 250
typedef struct {
char ch[maxlen];
int length;
}SString;
（4）串的模式匹配：確定子串的位置，
int index(SString S, SString T, int pos)
{
int i = pos, j = 1;
while (i <= S.length&&j <= T.length)
{
if (S.ch[i] == T.ch[j])
{
++i;
++j;
}
else
{
i = i - j + 2;
j = 1;
}
}
if (j > T.length)
{
return i - T.length;
}
else
{
return 0;
}
}
2）堆分配存盤
（1）存盤空間在執行程序中動態得到，
（2）堆分配存盤結構描述
typedef struct {
char *ch;
int length;
}HString;
3）塊鏈存盤
（1）每個結點被稱為塊，既可以存放一個字符，也可以存放多個字符，整個鏈表稱為塊鏈結構，
（2）當最后一個結點沒有被全部占滿時用#填充，
（3）存盤密度=串值所占存盤位/實際分配存盤位，
（4）塊鏈存盤結構描述
#define chunksize 50
typedef struct chunk {
char ch[chunksize];
struct chunk * next;
}chunk;
typedef struct {
chunk * head, *tail;
int curlen;
}LString;
3、串的模式匹配：確定子串的位置，
1）主串：包含字串的串，
2）子串：串中任意個連續的字符組成的子序列，
1）簡單模式匹配時間復雜度為O(nm)，n為主串長度，m為模式串長度，
2）KMP演算法
（1）原理：i指標不回溯，僅將子串向后滑動一個合適的位置，并從該位置開始和主串進行比較，該位置僅與子串本身結構有關，與主串無關，
（2）字串的前綴：除最后一個字符以外，字串的所有頭部子串，
（3）字串的后綴：除第一個字符以外，字串的所有尾部子串，
（4）部分匹配值：字串的前綴和后綴的最長相等前后綴長度，
例子：
'a'：前綴、后綴均為空集，最長相等前后綴長度為0，
'ab'：前綴為{a}，后綴為{b}，{a}∩{b}=Ø，最長相等前后綴長度為0，
'aba'：前綴為{a,ab}，后綴為{a,ba}，{a,ab}∩{a,ba}={a}，最長相等前后綴長度為1，
'abab'：前綴為{a,ab,aba}，后綴為{b,ab,bab}，{a,ab,aba}∩{b,ab,bab}={ab}，最長相等前后綴長度為2，
'ababa'：前綴為{a,ab,aba,abab}，后綴為{a,ba,aba,baba}，{a,ab,aba,abab}∩{a,ba,aba,baba}={a,aba}，最長相等前后綴長度為3，
（5）時間復雜度為O(n+m)，
（6）移動的位數=已匹配的字符數-對應的部分匹配值，
將部分匹配值寫成陣列的形式，求next陣列
void getnext(SString T, int next[])
{
int i = 1, j = 0;
next[i] = 0;
while (i<T.length)
{
if (j == 0 || T.ch[i] == T.ch[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
（7）KMP演算法
int kmpindex(SString S, SString T, int next[], int pos)
{
int i = pos, j = 1;
while (i<=S.length&&j<=T.length)
{
if (j == 0 || S.ch[i] == T.ch[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j > T.length)
{
return i - T.length;
}
else
{
return 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55361.html
標籤：其他
上一篇：CF1342C Yet Another Counting Problem
下一篇：堆疊的鏈接存盤