数据结构_串

github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E4%B8%B2.md

定义

• 特殊的线性表，每个元素都是字符
• 元素可以是零个或多个

常用操作

查找子串、串的相似度、截取、反转、最长公共子串、分词、回文

顺序实现

• 字符串的操作一般都不改变内存空间（例外：连接两个字符串），因此顺序存储整体效率更高
• 存储单元大小＝串真实长度＋1（"\0"占一个字节空间）
• 比较适合的操作：查找、截取

链式存储

• 类似插入、删除的操作是效率较高的，截取就不好了

经典算法

朴素的模式匹配算法

https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/simpleChuan.png

代码实现：

#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)是降低时间复杂度的关键（相对于双层循环）

KMP算法

KMP算法图解＋代码

---