数据结构与算法A 第四章字符串

字符串的基本概念

• 字符串是组成元素(结点)为单个字符(数字、文本字符或特定的符号)的线性表，简称“串”

• 字符串所包含的字符个数成为串的长度。空串：长度为零的串“”；空格串：“ ”

• 字符串的逻辑结构和线性表逻辑结构的区别：

  1. 字符串的数据对象约束为字符集
  2. 字符串的基本操作通常以“串的整体”为操作对象

• 字符串常数：用一对双撇号“xxxx”作为左右括号，中间字符个数有限

字符编码

• 字符类型是单字节（8 bits）类型

• 采用ASCII码对128个符号（字符集charset）进行编码

• 通用文字符号编码标准UNICODE

字符的编码顺序

• 字符编码表一般遵循“偏序编码规则”：根据字符的自然含义编码，使字符集中的编码顺序和其自然次序一致

• 字符偏序：根据字符的自然含义，某些字符间两两可以比较次序

• encode()是符号的ASCII编码(序号)的映射函数

• 对于字母而言，大小次序就是按照字典编目次序。e.g. “monday”<”sunday”<”tuesday”.”123”<”1234”<”23”

字符串ADT

• 子串：s1 = a0a1a2…an-1和s2 = b0b1b2…bm-1，（0 ≤ m ≤ n）若存在整数i (0 ≤ i ≤n-m)，使得bj = ai+j, j = 0,1,…,m-1同时成立，则称串s2是串s1的子串，或称s1包含串s2

• 真子串：子串非空且不是自身

class string  
{ 
private: 	 	// 字符串的存储结构在具体实现时定义
    char *str		// 字符串的数据表示
    int size			// 串的当前长度
public: 			// 字符串的运算集
    string(char *s = ""); 	// 创建一个空字符串
    string(char *s);		// 创建一个初值为s的字符串
    ~string ();  		// 消除该串实例
    int length();		// 返回串的长度
    int isEmpty();		// 判断串是否为空串
    void clear();			// 把串清空
    string append(char c);		// 在串尾添加字符
    string concatenate(char *s);	// 把串s连接在本串后面
    string copy(char*s); 		// 将一个串s拷贝到本串
    string insert(char c, int index);	// 往串中给定位置插字符
    // 从位置start开始搜索串寻找一个给定字符
    int find(char c, int start);		
    // 从位置s开始提取一个长度为len的子串
    string substr(int s, int len);     	
}

字符串的存储结构和实现

字符串的顺序存储

• 顺序存储：C++标准字符串。采用char S[M]的形式定义字符串变量，M是常量保持不变

• 串的结束标记：’\0’，长度为M的字符串实际最大容量的为(M-1)

• 标准字符串函数

  1. 串长函数：返回字符串的长度。int strlen(char *s);
  2. 串复制：将s2值复制给s1，返回指针指向s1。char *strcpy(char *s1, char *s2);
  3. 串拼接：将串s2拼接到s1的尾部。char *strcat(char *s1, char *s2);
  4. 串比较：int strcmp(char *s1, char *s2);（= ，>，<）
  5. (左)定位函数：c在s中第一次出现的位置。char *strchr(char *s, char c);
  6. 右定位函数：c在s中最后一次出现的位置。char *strrchr(char *s, char c);

字符串类class String的存储结构

• 字符串的长度动态变化，不适合采用动态链表形式

• 不再以字符数组char S[M]的形式出现，而采用一种动态变长的存储结构

• String类部分算子列表

• s2的长度>s1,将s2赋值给s1时，必须释放s1原有空间delete[] s1.str，然后在动态存储区开辟新的存储数组，再把s2的内容复制到新数组中

字符串运算的实现

C++标准串运算的实现

• 字符串的比较strcmp

int strcmp(char *d,char *s) 
{
    int i = 0;
    while (s[i] != '\0' && d[i] != '\0' )   
    {
        if (d[i] > s[i])
            return 1;
        else if (d[i] < s[i])
            return -1;
         i ++;
    }
    if(d[i] == '\0' && s[i] != '\0')
        return -1;
    else if (s[i] == '\0 '&& d[i] != '\0')
        return 1;
    return 0;
}

• 正向寻找字符

char *strchr(char *d,char ch) //查找ch在d中第一次出现的位置
{ 
    i = 0;
    while (d[i] != '\0' && d[i] != ch)  
        i++;   //跳过不是ch的字符
    if (d[i] == '\0')
        return '\0';   				 //表示失败
    else  
        return &d[i];
} 

• 反向寻找字符

char *strrchr(char *d,char ch)
{
    i = 0;
    while (d[i] != '\0')  
        i++;                       //找串尾
    while (i >= 0 && d[i] != ch) 
        i-- ;        //跳过不是ch的字符
    if (i < 0) 
        return '\0'  
    else  
        return &d[i]; 
}

String串运算的实现

• String串运算的实现

String::String(char *s)
{    
//先要确定新创建字符串实际需要的存储空间，s的类型为(char *)，作为新创字符串的初值。
//确定s的长度，用标准字符串函数strlen(s)计算长度
  size = strlen(s) ;  
      //然后在动态存储区开辟一块空间存储初值s，把结束字符也包括进来;
  str = new char[size＋1];
      //开辟空间不成功时，运行异常，退出
  assert(str != NULL); 
      //用标准字符串函数strcpy，将s完全复制到指针str所指的存储空间
  strcpy(str, s);
}

• 拼接算子

String String::operator+(String& s)
{   
  //把字符串s和本实例拼接成为一个长串返回
    String temp;    		//创建一个串temp
    int len;
    len = size + s.size; 		//准备工作，计算拼接后的长串的长度
    temp.str= new char[len+1];    //准备工作，开辟空间，为存放长串之用
    assert(temp.str!= NULL)；	//若开辟动态存储空间不成功，则退出
    temp.size= len;
    strcpy(temp.str,str); 		//字符串str（以’\0’结尾）存到temp
    strcat(temp.str,s.str); 		//再把参数s的str和本实例的str拼接为长串
    return temp;
}

• 赋值算子

String String::operator=(String& s)
{    
//参数s将被赋值到本串,若本串的串长和s的串长不同，则应该释放本串的str存储空间，并开辟新的空间
    if(size != s.size)
    {
        delete [] str ;  //释放原存储空间
        str = new char[s.size+1];
        assert(str != NULL)； //若开辟动态存储空间失败，则退出正常运行
        size = s.size;
    }
    strcpy(str,s.str);
    return *this; //返回本实例，作为String类的一个实例
}  

• 抽取子串函数

String String::Substr(int index,int count)
{    
    //取出一个子串返回，自下标index开始，长度为count 
    int i;
    //本串自下标index开始向右数直到串尾，长度为left
    int left = size – index; 	
    //自index到串尾的有效长度；
    String temp;
    char *p, *q;
    //若下标index值太大，超过本串实际串长，则返回空串
    if(index >= size)     
        // 注意不是index >= size - 1
        return temp; 
    if(count > left) 
    //若count超过自index以右的实际子串长度，则count变小
        count = left;
    temp.str = new char[count+1];     
    p = temp.str;  
    //p的内容是指针，指向目前暂无内容的字符数组首字符处
    q = &str[index]; 
    //q的内容是一指针，指向本实例串的str数组的下标index
    //q取出所指内容后，指针加1，用p所指的字符单元接受拷贝，指针加1
    for (i = 0; i < count; i++)
        *p++ = *q++; 
    *p = '\0'; 	
    //循环结束后，让temp.str的结尾为’\0’
    temp.size = count;
    return temp;
}

4.3 字符串的模式匹配

• 字符串的模式匹配：在文本(T)中寻找一个给定的模式(P)

• 任务：用给定的模板P，在目标字符串T中搜索与模板P全相同的一个子串，并返回P 和T匹配的第一个子串的首字符位置

• 模式匹配的分类：

  1. 精确匹配：如果在目标T中至少一处存在模式P，则称为匹配成功，否则失败
  • 模式中的?为通配符
  2. 近似匹配：如果模式P与目标T（或其子串）存在某种程度相似，则认为匹配成功
  • 常用衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。（编辑距离 Edit Distance）
  • 基本操作由字符串的插入、删除和替换三种操作来组成

朴素的模式匹配算法

• 从主串T的第一个字符起和模式串P的第一个字符进行比较。若相等，则继续比较T和P的后续字符，否则，从主串S的第“2”个字符起再重新和模式P的第“1”个字符进行比较

• 最佳情况：在目标的前M个位置上找到模式，时间复杂度O(M)

• 最差情况：模式与目标的每一个长度为M的子串进行比较。目标形如an, 模式形如am-1b。总比较次数：M(N-M+1)。时间复杂度：O(M*N)

#include "String.h"
#include <assert.h>
int NaiveStrMatching (const String & T,const String & P)
{
    int i = 0;                  // 模式的下标变量
    int j = 0;                  // 目标的下标变量
    int pLen = P.length()       // 模式的长度
    int tLen = T.length()       // 目标的长度
    if (tLen < pLen)            // 如果目标比模式短，匹配无法成功
    {
        return -1;
    }
    while (i < pLen && j < tLen)    // 反复比较对应字符来开始匹配
    {
        if(T[j] == P[i])
        {
            i++;
            j++;
        }
        else
        {
            j = j - i + 1;
            i = 0;
        }
    }
    if (i >= pLen)
    {
        return (j - pLen + 1);
    }
    else
    {
        return -1;
    }
}

字符串的特征向量KMP算法

• P中每个字符对应一个移位值k，该值仅依赖于模式P本身，与目标T无关

• 当某次比较出现Pi != Tj时，意味着满足：P(0…i-1)=T(j-i…j-1)成立

  1. 如果P(0…i-2) = P(1…i-1)成立，即模式后移一位后P(0…i-2)=T(j-i+1…j-1)。
  2. 如果不满足可依据需查找P(0…i-3)与P(2…i-1)是否相等
  3. 以此类推必然可以找到某个值k使得P(0…i-k-1) = P(k…i-1)成立，此时把模式右移k位开始下一次匹配

• P的前缀子串(“首串”)：P的前K个字符组成的子串P(0…k-1)。i位置的后缀子串(“尾串”)：P在i之前的k个字符组成的子串P(i-k…i-1)

• 对于Pi而言，一旦与目标Tj失配时，模式的下标从位置i移动到位置k，Pk直接与Tj比较，而跳过了P(0…k-1)。如果把目标Tj看做是不动的，则模式向右滑动了i-k位

• 把对应模式中每个字符Pi的这个k值称其为特征数ni，即P(0…i-1)中最大相同前缀子串和后缀子串。所有特征数组成了模式的一个特征向量，next数组。

• 特征向量 N 用来表示模板 P 的字符分布特征，简称 N 向量和 P 同长，由m个特征数n0 …nm-1非负整数组成，记为N = n0n1n2n3……nm-1。k就是要求的特征数ni

• 特征数ni (-1 ≤ ni ≤ i )是递归定义的，定义如下：

  1. n0 ←-1，对于i > 0的ni ，假定已知前一位置的特征数 ni-1 ，并且ni-1 = k ；
  2. 如果pi = pk ，则ni ← k＋1 ；
  3. 当pi ≠ pk 且 k ≠ 0时，则 令k ← nk ; 循环直到条件不满足；
  4. 当pi ≠ pk 且 k = 0时，则 ni = 0;

• 个人理解求next数组方法：

  1. 第零和一位：next[0] = -1 ;next[1] = 0
  2. 非第零和一位：看第0位开始的k个数和从前一位往回数k个数是否相同。找出最大的k
  3. 如果找不到，k = 0

int* findNext (string P)
{
    int i,k;
    int m = P.length();             // m为模板P的长度
    int* next = new int[m];         // 动态存储区开辟整数数组
    next[0] = -1;
    i = 0;
    k = -1;
    while (i < m - 1)               // 若写成i < m会越界
    {
        // 如果不等，采用KMP方法找首尾子串
        while (K >= 0 && p[k] != p[i])
        {
            k = next[k];            // k递归的向前找
        }
        i++;
        k++;
        next[i] = k;
    }
    return next;
}

• 求出的next数组还可以进一步优化。若求出next[i]=k，当匹配时发现Pi!=Tj时，按照特征向量的意义，该把模式右移i-k位，用Pk与Tj比较。如果Pi!=Pk，则Tj!=Pk，还需再右移，用Pnext[k]来与Tj比较

int* findNext(string P)
{
    int i = 0;
    int k = -1;
    int m = P.length();                 // m为字符串P的长度
    assert(m > 0);                      // m=0退出
    int * next = new int[m];            // 动态存储区开辟整数数组
    assert(next != 0)                   // 若开辟存储区域失败，退出
    next[0] = -1;
    while (i < m)
    {   //计算i=1...m-1的next值
        while (k >= 0 && p[i] != p[k])  // 求最大首尾子串
        {
            k = next[k];
        }
        i++;
        k++;
        if (i == m)
        {
            break;
        }
        if (p[i] == p[k])
        {
            next[i] = next[k];          // p[i]和p[k]相等，优化
        }
        else
        {
            next[i] = k;                // 不需要优化，就是位置i的首尾子串长度
        }
    }
    return next;
}

KMP模式匹配算法

• KMP的算法的时间复杂性为O(N)。求next数组的时间为O(m)。因此，KMP算法的时间为Ｏ(n+m)。

int KMPStrMatching (const String & T,const String & P,int * N)
{
    int i = 0;
    int j = 0;
    int pLen = P.length();
    int tLen = T.length();
    if (tLen < pLen)
    {
        return -1;
    }
    while (i < pLen && j < tLen)
    {
        if (i == -1 || T[j] == P[j])
        {
            i++;
            j++;
        }
        else
        {
            i = N[i];
        }
    }
    if (i >= pLen)
    {
        return j - pLen + 1;
    }
    else
    {
        return -1;
    }
}

---

第四章 字符串 OJ作业

1:全在其中

/*描述
你设计了一个新的加密技术，可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。
由于专利问题，我们将不会详细讨论如何在原有信息中产生和插入字符串。不过，为了验证你的方法，有必要写一个程序来验证原来的信息是否全在最后的字符串之中。
给定两个字符串s和t，你需要判断s是否是t的“子列”。也就是说，如果你去掉t中的某些字符，剩下字符将连接而成为s。
输入
输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000。
输出
对于每个测试样例，如果s是t的“子列”，则输出”Yes”，否则输出”No”
样例输入
sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter
样例输出
Yes
No
Yes
No
*/
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

bool f(string s, string t, int ls, int lt)
{
    if (s.empty())
    {
        return true;
    }
    if (t.empty())
    {
        return false;
    }
    int i = 0;
    int j = 0;
    while (i < ls && j < lt)
    {
        if (s[i] == t[j])
        {
            i++;
        }
        j++;
    }
    return (i == ls);
}

int main()
{
    string result1 = "Yes";
    string result2 = "No";
    string s, t;
    while (cin >> s >> t)
    {
        int ls, lt;
        ls = s.length();
        lt = t.length();
        if (f(s, t, ls, lt) == true)
        {
            cout << result1 << endl;
        }
        else
        {
            cout << result2 << endl;
        }
    }
    return 0;
}

2:字符串乘方

/*描述
给定两个字符串a和b,我们定义a*b为他们的连接。例如，如果a=”abc” 而b=”def”， 则a*b=”abcdef”。 如果我们将连接考虑成乘法，
一个非负整数的乘方将用一种通常的方式定义：a^0=””(空字符串)，a^(n+1)=a*(a^n)。
输入
每一个测试样例是一行可打印的字符作为输入，用s表示。s的长度至少为1，且不会超过一百万。最后的测试样例后面将是一个点号作为一行。
输出
对于每一个s，你应该打印最大的n，使得存在一个a，让s=a^n
样例输入
abcd
aaaa
ababab
.
样例输出
1
4
3
提示
本问题输入量很大，请用scanf代替cin，从而避免超时。*/
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int f(string s)
{
    int l = s.length();
    for (int a = 1; a <= l; a++)
    {
        if (l % a == 0)
        {
            bool isValid = true;
            for (int i = a; i < l; i++)
            {
                if (s[i] != s[i % a])
                {
                    isValid = false;
                    break;
                }
            }
            if (isValid)
            {
                return l / a;
            }
        }
    }

    return 1;
}

int main()
{
    char s[1000005];
    while (scanf("%s", s) && s[0] != '.') 
    {
        cout << f(s) << endl;
    }
    return 0;
}

3:合格的字符串

/*描述
老师给小学生门布置了一些作业，让它们按照一个模版写一些字符串交上来，
同学们把作业交上来了，问题来了，这么多的作业老师批改不过来，现在请你帮老师
写一个程序，帮助老师确定各个字符串是否合格。
首先老师有一个匹配模版，比如是“aa[123]bb”这一个字符串，同学们交的各种
作业字符串如aa1bb、aa2bb、aa3bb都算是正确匹配看，而aacbb就是错误的字符串。
（即待查字符串对应于模版方括号内的部分，应该为方括号内字符串的一个子字符）。
我们需要做的就是按照模版，找出正确的字符串和所在的行。
输入
输入的第一行为一个整数n，表示有多少个学生的作业，即有多少行需要检查的字符串。（1<=n<=50)
中间为n行字符串，代表着n个学生们写的作业。每个字符串长度小于50。
最后一行为1行字符串，代表着老师给的匹配模板。
输出
输出合格的字符串的行号和该字符串。（中间以空格隔开）
样例输入
4
Aab
a2B
ab
ABB
a[a2b]b
样例输出
1 Aab
2 a2B
4 ABB
提示
被检测的字符串中只有数字和字母。*/
#include <iostream>
#include <string>
using namespace std;

bool f(const string answer, string pattern)
{
    int l1 = answer.length();
    int l2 = pattern.length();
    int i = 0, j = 0;
    while (i < l1 && j < l2)
    {
        if (pattern[j] != '[') // 非方括号直接匹配
        {
            if (answer[i] != pattern[j])
            {
                return false; // 不匹配直接返回false
            }
            i++;
            j++;
        }
        else
        {
            // 处理方括号内的字符集
            j++; // 跳过'['
            bool matched = false;
            while (pattern[j] != ']') // 直到找到']'
            {
                if (answer[i] == pattern[j]) // 找到匹配的字符
                {
                    matched = true;
                }
                j++;
            }
            if (!matched)
            {
                return false; // 没有找到匹配的字符，返回false
            }
            i++;
            j++;
        }
    }
    return i == l1 && j == l2; // 确保字符串都匹配完
}

int main()
{
    int n;
    cin >> n;
    string answer[51];
    for (int i = 0; i < n; i++)
    {
        cin >> answer[i];
    }
    string pattern;
    cin >> pattern;
    for (int i = 1; i <= n; i++)
    {
        if (f(answer[i - 1], pattern))
        {
            cout << i << " " << answer[i - 1] << endl;
        }
    }
    return 0;
}