当你做某件事的时候，一旦想要求快，就表示你再不关心它，而想去做别的事。

一、串的定义

串是由零个或多个字符组成的有限序列，又名叫字符串。

一般记为s=”a1 a2 a3 …an”(n>=0)。n称为串的长度，零个字符的串称为空串（null string）。

需要知道的几个概念

空格串:是只包含空格的串。空格串是有内容有长度的，而且可以不止一个空格。
子串和主串：串中任意个数的连续字符组成的子序列成为该串的子串，相应的，包含子串的串称为主串。如“over”是“lover”的子串，“end”是“friend”的子串灯。

二、串的比较

串的比较是通过组成串的字符之间的编码来进行的，而字符编码指的是字符在对应字符集（如ASCII码或者Unicode编码）中的序号。

两个串不相等时，通过下面的定义来判断它们的大小：

给定两个串：s=a”1a2…an”，t=“b1b2…bm”，当满足一下条件之一时，s<t。

n<m，且ai=bi(i=1，2，3，…，n)。
存在某个k<=min(m，n),使得ai=bi(i=1,2,3,…,k-1)，ak<bk。

三、串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，串中的元素是字符。因此对串的基本操作与线性表是有很大差别的。线性表更关注单个元素的操作，比如查找一个元素，删除或插入一个元素，而串更多的是查找子串的位置，得到指定位置的子串，替换子串等操作。

ADT 串 (string)
DATA
    串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
    StrAssign(T , *chars):生成一个其值等于字符串常量chars的串T。
    StrCopy(T ， S) :串S存在，由串S复制得串T。
    ClearString(S):串S存在，将串清空
    StringEmpty(S):若串S为空，返回true，否则返回false。
    StrLength(S):返回串S的元素个数，即串的长度。
    StrCompare(S,T):若S>T,返回值>0，若相等，返回0，若小于，返回值<0
    Concat(T,S1,S2):用T返回由S1和S2连接而成的新串。
    SubString(Sub,S,pos,len):串S存在，1<=pos<=StrLength(s),且0<=LEN<=StrLength(S) - pos + 1,用sub返回串S的第pos个字符串起长度为len的子串。
    Index(S,T,pos):串S和T存在，T是非空串，1<=pos<=StrLength(s)。若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0。
    Replace(S,T,V)：串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠子串。
    StrInsert（S，pos，T）：串S和T存在，1<=pos<=StrLength(S) +1。在串S的第pos个字符之前插入串T。
    StrDelete（S，pos，len）：串S存在，1<=pos<=StrLength(S) - len + 1。从串S中删除第pos个字符起长度为len的子串。
endADT

其实，在java里还有ToLower、IndexOf等操作，它们是对基本操作的拓展函数。

操作Index的实现算法

/*T为非空串，若主串S第pos个字符后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0 */
int Index(String S,String T,int pos){
    int ,m,i;
    String sub;
    if(pos > 0){
        n = StrLength(S);    //获取S长度
        m = StrLength(T);
        i = pos;
        while(i <= n-m+1){
            SubString(sub,S,i,m);
            if(StrCompare(sub,T) != 0){
                    ++i;
               }else{
                    return i;
               }
       }
   }
    return 0;
}

四、串的存储结构

串的存储结构与线性表相同，分为顺序存储结构和链式存储结构。

1、串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。一般是用定长数组来定义。

2、串的链式存储结构

串的链式存储结构，与线性表是相似的，由于串中的每个元素数据是字符，如果只是一个结点对应一个字符的话，就会存在很大的空间浪费。因此需要考虑一个结点是存放一个字符还是多个字符，若最后一个结点未占满，则可以用“#”或其他非串值字符补全。但串的链式存储结构除了在链接串与串操作时有一定方便外，总的来说不如顺序存储灵活，性能也没有顺序存储结构好。

五、朴素的模式匹配算法

子串的定位操作通常称为串的模式匹配。

1、主串中找到子串的位置

如从主串s=“goodgoogle”中，找到t=“google”这个子串的位置。通常是对主串中的每一个字符作为子串开头，与要匹配的字符串进行匹配，对主串做一个大循环，每个字符开头做t的长度的小循环，直到匹配成功或者全部遍历完成为止。

/*返回子串T在主串S中的pos个字符后的位置。不存在则返回0。*/
int Index(String S,String T,int pos){
    int i = pos;
    int j = 1;
    while(i <=S[0] && j <=T[0]){
        if(S[i] == T[j]){
            ++i;
            ++j;
         }else{
                i = i - j + 2;
                j = 1;
         }
   }
   if(j > T[0]){
        return i - T[0];
     }else
        return 0;
}