06、数据结构与算法C++：串-程序员快看-教程，程序员编程资料站

串

我们经常需要存储和处理字符信息，因此就有了“串”这个数据结构。

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

串一般记为s=“a1a2......an” s = “ a 1 a 2 . . . . . . a n ” s 是串的名称。串中的字符数目 n 称
为串的长度，当n为0是称为空串。

空格串 只包含空格的串，空格串不是空串，它可以包含多个空格。

子串与主串 串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。

串的比较

数值很容易进行比较，那么字符串如何进行比较呢？
对于给定的两个串s=“a1a2......an” s = “ a 1 a 2 . . . . . . a n ” ，t=“b1b2......bn” t = “ b 1 b 2 . . . . . . b n ” 当满足以下条件之一时，s<t s < t :

1、 n<mn<m，且ai=bi(i=1,2,3,......,n)ai=bi(i=1,2,3,......,n)；
2、存在某个k⩽min(m,n)k⩽min(m,n)，使得ai=bi(i=1,2,3,......,k)，ak<bkai=bi(i=1,2,3,......,k)，ak<bk；

串的顺序存储结构

串的顺序存储结构我们用数组来实现，为了更好判断串的截止，我们一般用“\0”表示串值的终结。还有一种方法是将串的长度保存在数组的0下标的位置。

串的链式存储结构

串的链式存储结构，与线性表是相似的。只不过串链表结点中的数据元素存储的是一个或多个字符。当结点中的数据元素未被占满时可以用“#”或其他非率值字符补全。总体来说，串的链式存储结构不如串的顺序存储结构来的实用。

串的模式匹配与KMP算法

在串的操作中我们经常需要查找子串在主串中的位置，比如查找一个词在一篇文章中的位置等，像这样子串的定位操作通常称做串的模式匹配。最简单的做法就是暴力匹配，就是重第一个位置开始进行匹配，匹配不成功就移动到主串第二个位置进行匹配。这样做对于两个长度分别为n和m串的模式匹配的时间复杂度就为O(n∗m) O ( n ∗ m ) 。能不能有更好的匹配方案呢？
我们先来举个栗子，主串S="abcdeacdfe" S =" a b c d e a c d f e " ，待匹配串T="abcdx" T =" a b c d x " 。我们看到两个字符串的前四个字符相同，第5个字符不同，且前四个字符各不相同，所以我们第二次匹配可以从主串的第5个字符开始，因为T中“a”与”b”“c”“d”不同而子串与主串前四位字符又相同，所以T从S的第二到第四的位置开始也不能与主串匹配。这样就省去了不少的匹配过程，提高了效率。
那么如何又如何让计算机知道下次从哪里开始匹配呢？这里我们介绍一个模式匹配算法，克努特一莫里斯一普拉特算法，简称 KMP 算法。KMP 算法通过T 串各个位置的 j 值的变化定义为一个数组 next来确定下个匹配位置。next数组只和代匹配串T有关，与主串无关，其定义如下：

next[j]=*******−1,当j=0时Max{ k|0<k<j,‘p1...′k−1=‘pj−k+1...p′j−1当此集合不空时}0，其他情况 n e x t [ j ] = { − 1 , 当 j = 0 时 M a x { k | 0 < k < j , ‘ p 1 . . . k − 1 ′ = ‘ p j − k + 1 . . . p j − 1 ′ 当此集合不空时 } 0 ，其他情况

数组 next创建代码如下：

void get_next(string T,int * next)
{
    int i, j;
    i = 0;
    j = -1;
    next[0] = -1;
    while (i <(int)T.length())
    {
        if (-1 == j || T[i] == T[j])
        {
            next[++i] = ++j;
        }
        else
        {
            j = next[j]; //若字符不相同.则 j 值回溯 
        }
    }
    cout << endl;
}

KMP具体代码如下：

#include<iostream>
#include<string>

using namespace std;

void get_next(string T, int * next);
int KMP(string S, string T);
int main()
{
    string S, T;
    cout << "请输入主串：" ;
    cin >> S;
    cout << "请输入要匹配字符串：" ;
    cin >> T;
    int k = KMP(S, T);
    if (k!=-1)
    {
        cout << "在主串上，位置为" << k<<endl;
    }
    else
    {
        cout << "不匹配" << endl;
    }
    system("pause");
    return 0;
}

void get_next(string T,int * next)
{
    int i, j;
    i = 0;
    j = -1;
    next[0] = -1;
    while (i <(int)T.length())
    {
        if (-1 == j || T[i] == T[j])
        {
            next[++i] = ++j;
        }
        else
        {
            j = next[j]; //若字符不相同.则 j 值回溯 
        }
    }
}
int KMP(string S, string T)
{
    int i = 0;//主串位置
    int j = 0;//模式串位置
    int* next = new int[T.length()+1];
    get_next(T,next);
    while ((i < (int)S.length())&&(j < (int)T.length()))
    {
        if (-1 == j || S[i] == T[j])//当j为 - 1时，要移动的是i，当然j也要归0
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    delete [] next;
    if (j ==(int) T.length()) 
    {

        return i - j;

     }
    else 
    {
       return -1;
     }
}

在VS上运行结果如下：