数据结构之串

---

1、串的定义和实现 1.1、串的定义

 串是由零个或多个字符组成的有限序列。一般记为 S = ‘a₁a₂…a_n’ (n>=0)

 其中，a_i 可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。n = 0 时称为空串（用 ∅ 表示)。

 串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

1.2、串的存储结构

 串的存储结构有：1. 定长顺序存储表示（定长数组）； 2. 堆分配存储表示（动态数组）； 3. 块链存储表示。

---

2、串的模式匹配 2.1、朴素算法

设主串的长度为 n，模式串的长度为 m。

 算法思想：从主串 S 的第一个字符起（下标均从 1 开始），与模式 T 的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式字符比较；以此类推，直至模式 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等，则称匹配成功，函数值为与模式 T 中第一个字符相等的字符在主串 S 中的序号，否则称匹配不成功，函数值为零。时间复杂度：O(mn)

#include 
using namespace std;

const int N = 1010, M = 1010;
int n, m;
char S[N], P[M]; //主串为S[N]，模式串为P[M]

//若匹配成功, 返回 P 在 S 中的第一个字符的序号;否则,返回 0 代表没有匹配成功
int Index(char S[], char P[])
{
    int i = 1, j = 1; // 开始分别指向各自首字符
    while (i <= n && j <= m)
    {
        if (S[i] == P[j])
        {                       // 继续比较后继字符
            i++;	j++;
        }else{                  // 指针后退重新开始匹配
            i = i - j + 2;      // i 回退的位置：特殊值法确定 i 的表达式
            j = 1;
        }
    }
    if (j > m)
        return i - m;  // 匹配成功 i,j跨度一致
    else
        return 0;
}
int main()
{
    cout << "请分别输入 主串长度 与 主串：" << endl;
    cin >> n >> S + 1;
    cout << "请分别输入 模式串长度 与 模式串：" << endl;
    cin >> m >> P + 1;

    cout << Index(S, P) << endl;
    return 0;
}

动画演示

2.2、KMP算法

 暴力匹配低效的根源：每趟匹配失败都是主串后移一位再与模式串从头开始比较，而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较。

2.2.1、前言

前缀、后缀、部分匹配值

• 前缀：指除最后一个字符以外，字符串的所有头部子串；
• 后缀：指除第一个字符外，字符串的所有尾部子串；
• 部分匹配值：指字符串的前缀和后缀的最长相等前后缀长度。

以"ababa"为例：

部分匹配值的作用

 主串为 ababcabcacbab，子串为abcac。子串的部分匹配值为00010，构建PM表：

编号	1	2	3	4	5
T	a	b	c	a	c
PM	0	0	0	1	0

下面用PM表来进行字符串匹配：

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串	a	b	c

第一趟匹配过程：
  发现 c 与 a 不匹配，前面的 2 个字符 ‘ab’ 是匹配的，查表可知，最后一个匹配字符 b 对应的部分匹配值为 0，因此按照如下公式算出子串需要向后移动的位数：
         移动位数 = 已匹配的字符数 - 对应的部分匹配值
顾将子串向后移动 2 位，如下进行第二趟匹配：

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串			a	b	c	a	c

 发现 c 与 b 不匹配，前面 4 个字符 ‘abca’ 是匹配的，最后一个匹配字符 a 对应的部分匹配值为 1，4-1=3，将子串向后移动 3 位，如下进行第三趟匹配：

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串						a	b	c	a	c

第三趟匹配过程：
  子串全部比较完成，匹配成功。整个匹配过程中，主串始终没有回退，故 KMP 算法时间复杂度为O（n+m）。

注意点：尽管普通模式匹配的时间复杂度是O（mn），KMP 算法的时间复杂度是O（m + n），但在一般情况下，普通模式匹配的实际执行时间近似为O（m + n），因此至今仍被采用。KMP 算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点是主串不回溯。

2.2.2、KMP原理

        移动位数 = 已匹配的字符数 - 对应的部分匹配值

如上述第二趟匹配时当 c 与 b 匹配失败后为什么是向后移动 3 位！因为已匹配 abca 的最长相等前后缀长度为 1，a 与 b、c 均不同，与后缀 a 相同（亦与对应位置的主串相同），此时用子串前缀后面的元素与主串匹配失败的元素开始比较岂不又快又准。

对算法的改进方法：

上述公式写成：Move = (j - 1) - PM[j - 1]。(j 是匹配失败时子串对应字符的位序)

为了更加方便，将 PM 表右移一位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可。右移一位得到 next 数组：

编号	1	2	3	4	5
T	a	b	c	a	c
next	-1	0	0	0	1

需要注意的是：

1）第一个元素右移以后空缺的用 -1 来填充，因为若是第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串移动的位数。

2）最后一个元素在右移的过程中溢出，因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，故可以舍去。
这样，上式就改写为 ：

Move = （ j - 1 ）- next[ j ]

相当于将子串的比较指针 j 回退到如下公式：

j = j - Move = j - ( ( j - 1 ) - next[ j ] ) = next[ j ] + 1

有时为了使公式更加简洁、计算简单，将 next 数组整体 +1。
因此，上述子串的 next 数组也可以写成：

编号	1	2	3	4	5
T	a	b	c	a	c
next	0	1	1	1	2

最终得到子串指针变化公式： j = next [ j ]。

next [ j ] 的含义是：在子串的第 j 个字符与主串发生失配时，则跳到子串的 next [ j ]位置重新与主串当前位置进行比较。

next 数组的一般公式：（详细推导过程可参考严蔚敏版教材）

根据一般公式编写代码较为容易。

举个例子加深对 next 数组的理解：

  如下模式串中已求得 6 个字符的 next 值，现求 next[7]，因为 next[6] = 3，又 p₆ ≠ neq ​= p₃， 则需比较 p₆ 和 p₁（因 next[3] = 1)，由于 p₆ ≠ neq ​= p₁，而next[1] = 0，所以next[7] = 1。

求next[8]，因p₇ = p₁，则next[8] = next[7]+1=2；

求next[9]，因p₈ = p₂，则next[9] = 3。

j	1	2	3	4	5	6	7	8	9
模式	a	b	a	a	b	c	a	b	a
next[j]	0	1	1	2	2	3	?	?	?

求解 next 数组的代码如下：

void get_next(String T, int *next){
    int i=1, j=0;
    next[1]=0;
    while(i < T.length){  T[0] 存储串长度
        if(j==0 || T[i]==T[j]){
            ++i;++j;
            next[i] = j;  // 若pi = pj,则next[j+1] = next[j] + 1;
        }
        else
            j = next[j];    //若字符不相同，则j值回溯
    }
}

KMP模式匹配代码：

int Index_KMP(String  S, String T, int *next){
    int i = 1, j = 1;
    while(i <= S.length && j <= T.length){
        if(j ==0 || S[i] == T[j]){
            ++i;++j;      // 继续比较后继字符
        }else{
            j = next[j];  // 模式串向右移动
        }
    }
    
    if(j > T.length)
        return i - T.length; // 匹配成功
    else
        return 0;
}

2.3、改进的KMP

模式串 ‘aaaab’ 在和主串 ‘aaabaaaab’ 进行匹配时：

主串	a	a	a	b	a	a	a	a	b
模式	a	a	a	a	b
j	1	2	3	4	5
next[j]	0	1	2	3	4
nextval[j]	0	0	0	0	4

 要改进的根源在于不应该出现 p_j = p_next[j]。理由是：当 p_j ≠ neq ​= s_j 时，下次匹配必然是 p_next[j] 跟 s_j 比较，如果 p_j = p_next[j] ，则相当于拿一个和 p_j 相等的字符跟 s_j 比较，这必然导致继续失配，这样的比较毫无意义。修正方法为将 next[j] 修正为 next[ next[ j ] ]，直至两者不相等为止，更新后的数组命名为 nextval。

void get_nextval(String T, int *next){
    int i=1, j=0;
    nextval[1]=0;
    while(i < T.length){  
        if(j==0 || T[i]==T[j]){
            ++i; ++j;
            
            if(T[i] != T[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];    //若字符不相同，则j值回溯
    }
}

---

3、串的习题 3.1、选择题

01、串 S = ‘ababaaababaa’，其 next 数组值为【C】。

A. 01234567899  B. 012121111212  C. 011234223456  D. 0123012322345

---

02、串 ‘ababaaababaa’ 的 next 数组为【C】。

A. -1，0，1，2，3，4，5，6，7，8，8，8

B. -1，0，1，0，1，0，0，0，0，1，0，1

C. -1，0，0，1，2，3，1，1，2，3，4，5

D. -1，0，1，2，-1，0，1，2，1，1，2，3

注意：在实际 KMP 算法中，为了使公式更简洁、计算简单，如果串的位序是从 1 开始的，则next 数组才需要整体加 1；如果串的位序是从 0 开始的，则next数组不需要整体加 1。但 从 PM 到 next 均需要右移一位。

---

03、串 ‘ababaaababaa’ 的 nextval 数组为【C】。
A. 0，1，0，1，1，2，0，1，0，1，0，2
B. 0，1，0，1，1，4，1，1，0，1，0，2

C. 0，1，0，1，0，4，2，1，0，1，0，4

D. 0，1，1，1，0，2，1，1，0，1，0，4

---

04、已知字符串 S 为 ‘abaabaabacacaabaabcc’  模式串 t 为’abaabc’。采用KMP算法进行匹配，第一次出现“失配”时，i = j = 5，则下次开始匹配时，i 和 j 的值分别是【C】。

A. i = 1, j = 0    B. i = 5, j = 0   C. i = 5, j = 2   D. i = 6, j = 2

---

05、设主串 T = ‘abaabaabcabaabc’，模式串 S = ‘abaabc’，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是【B】。
A. 9    B. 10    C.12    D.15

---

---

3.2、编程题 3.2.1、最少添加字符数

原题链接：牛客网—最少添加字符串

思路：

分三种情况：

• 情况一：一个字符，答案是1，加上一个字符就可以了
• 情况二：两个字符，判断一下这两个字符是不是一样的，如果相同，答案就是字符串的长度，因为需要再加上本字符串，如果不同答案就是1，只用把第一个字符加上就可以了。
• 情况三：多个字符，字符串最后一个位置的next数组，因为next数组的含义是前缀与后缀的最大匹配长度。所以答案是字符串长度减 next[str.length()] 再减1。

#include
#include
#include
using namespace std;

int getNext(string str) {
	vector next(str.size());
	next[0] = -1; //人为规定，0号位置的值是-1
	next[1] = 0;
	int i = 2; // 从2开始遍历str
	int val = 0; // val既用来作为下标访问，也作为值
	while (i < next.size()) {
		if (str[i - 1] == str[val]) {
			next[i++] = ++val;
		}
		else if (val > 0) {
			val = next[val]; // 取出前一个next数组的值
		}
		else {
			next[i++] = 0;
		}
	}
	return next[str.size() - 1];
}

int main() {
	string str;
	cin >> str;
	int ans = 0;
	if (str.size() == 0) {
		cout << 0;
		return 0;
	}
	else if (str.size() == 1) {
		ans = str.size() + str.size();
	}
	else if (str.size() == 2) {
		ans = str[0] == str[1] ? str.size() + 1 : str.size() + str.size();
	}
	else {
		int next = getNext(str);
		ans = str.size() + str.size() -1 - next;
	}
	ans -= str.size();
	cout << ans;
	return 0;
}

3.2.2、KMP练习题集

参考博客：KMP练习题集

---

4、串的处理 4.1. 无重复字符的最长子串

4.1.1 题目来源: LeetCode_无重复字符的最长子串

4.1.2 题目内容:

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
4.1.3 题目示例：

示例 1：
 
 输入: s = “pwwkew”
 输出: 3
 
 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
4.1.4 求解代码：

public class Main {
	private static Scanner in;

	public static void main(String[] args) {
		in = new Scanner(System.in);
		String str = in.nextLine();
		System.out.println(lengthOfLongestSubstring(str));
		in.close();
	}

	
	public static int lengthOfLongestSubstring(String s) {
		// 哈希集合，记录每个字符是否出现过(去重)
		Set hashSet = new HashSet();
		int n = s.length();
		// 右指针,初始值为 0,指向首位字符,窗口大小为 1
		int rk = 0, ans = 0;
		for (int i = 0; i < n; i++) { // i就是左指针
			if (i != 0) //等于零时,无滑动窗口，无值,需要初始化第一个窗口
				hashSet.remove(s.charAt(i - 1));
			while (rk < n && !hashSet.contains(s.charAt(rk))) {
				hashSet.add(s.charAt(rk));
				rk++;
			}
			// 第 i 到 rk 个字符是一个极长的无重复字符子串
			ans = Math.max(ans, rk - i);
		}

		return ans;
	}
}

4.1.5 思路补充

1. 子串必定连续,，不包含重复字符的子串，意味着在原串中有一段区间内子串均不一样。符合题意的子串可能有多种，依题意，我们需要找出长度最长的子串。
2. 区间内子串无重复，区间问题采用滑动窗口解决，即使用双指针：左指针先指向原串最左端，右指针从左往右扫描，同时，借助 hashSet 的去重功能来判断右指针指向的字符是否在区间内。（注意点：左指针移动，窗口便更新了，此时需要从集合中移除其对应字符。右指针继续右移，以找到新的区间，同时更新最大长度）

1.6 官方题解

---

4.2. 最长回文子串

4.2.1 题目来源: LeetCode_最长回文子串

4.2.2 题目内容:

给你一个字符串 s，找到 s 中最长的回文子串。
4.2.3 题目示例：

示例 1：
 输入：s = “babad”
 输出：“bab”
 解释：“aba” 同样是符合题意的答案。

4.2.4 求解代码：

public class Main {
	private static Scanner in;

	public static void main(String[] args) {
		in = new Scanner(System.in);
		String str = in.nextLine();
		System.out.println(longestPalindrome(str));
		in.close();
	}

	
	public static String longestPalindrome(String s) {
		if (s == null || s.length() < 1)
			return "";

		int start = 0, end = 0;  // 记录最长回文串的左右边界
		for (int i = 0; i < s.length(); i++) {
			int len1 = expandAroundCenter(s, i, i);  // 长度为一的边界情况
			int len2 = expandAroundCenter(s, i, i + 1); // 长度为二的边界情况
			int len = Math.max(len1, len2);  // 每次枚举后，取两种情况最大值
			if (len > end - start) {   //固定每次枚举回文串的左右边界
				
				start = i - (len - 1) / 2; 
				end = i + len / 2;
			}
		}
		return s.substring(start, end + 1);
	}

	public static int expandAroundCenter(String s, int left, int right) {
		while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
			--left;
			++right;
		}
		
		return right - left - 1;
	}
}

4.2.5 思路补充

 首先，回文串一定是关于其回文中心对称的。原串中也可能会包含多个回文串，需要求出最长的那个。既然关于回文中心对称，则可以从回文中心向两边扩展，直到不符合条件为止，再用双指针记录最长回文串对应的左右边界。并将每次枚举获得的新回文串长度与双指针的间距对比，以此找到最长回文串

 力扣给出的回文串状态转移方程:

2.6 官方题解

---

4.3. 最长公共前缀

4.3.1 题目来源: LeetCode_最长公共前缀

4.3.2 题目内容:

编写一个函数来查找字符串数组中的最长公共前缀。
 
如果不存在公共前缀，返回空字符串 “”。
4.3.3 题目示例：

示例 1：
 
 输入：strs = [“flower”,“flow”,“flight”]
 输出：“fl”
4.3.4 求解代码：

	
	public static String longestCommonPrefix(String[] strs) {
		if (strs == null || strs.length == 0)
			return "";
		int minLength = Integer.MAX_VALUE;
		for (String str : strs) {
			minLength = Math.min(minLength, str.length());
		}

		int low = 0, high = minLength;

		while (low < high) {
			int mid = low + high + 1 >> 1; // 答案在右区间向上取整

			if (isCommonPrefix(strs, mid))
				low = mid;
			else
				high = mid - 1;
		}
		return strs[0].substring(0, low);
	}

	private static boolean isCommonPrefix(String[] strs, int mid) {
		String str0 = strs[0].substring(0, mid);
		for (String str : strs) {
			for (int i = 0; i < mid; i++) {
				
				if (str.charAt(i) != str0.charAt(i))
					return false;
			}
		}
		return true;
	}

4.3.5 思路补充

 公共前缀，顾名思义，一定是 n 个字符串前 x 长度的字符均一致。所以，最长公共前缀的长度一定不超过字符串数组中最短字符的长度。因为是前缀，每次都是从下标零开始的，故而可采用二分搜索，找到符合要求的最长的长度即可。
  二分算法总结

3.6 官方题解

---

4.4. 最长公共子序列

4.4.1 题目来源: LeetCode_最长公共子序列

4.4.2 题目内容:

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 
 
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
4.4.3 题目示例：

示例 1：
 
输入：text1 = “abcde”, text2 = “ace”
输出：3
 
解释：最长公共子序列是 “ace” ，它的长度为 3 。
4.4.4 求解代码：

public class Main {
	private static Scanner in;

	public static void main(String[] args) {
		in = new Scanner(System.in);

		String text1 = in.next();
		String text2 = in.next();

		System.out.println(longestCommonSubsequence(text1, text2));
		in.close();
	}

	public static int longestCommonSubsequence(String text1, String text2) {
		int m = text1.length(), n = text2.length();
		int[][] dp = new int[m + 1][n + 1];
		
		for(int i = 1;i<=m;i++) {
			for(int j=1;j<=n;j++) {
				if(text1.charAt(i-1) == text2.charAt(j-1))
					dp[i][j] = dp[i-1][j-1] + 1;
				else
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}
		return dp[m][n];
	}
}

4.4.5 官方题解

---

4.5. 最长递增子序列

4.5.1 题目来源: LeetCode_最长递增子序列

4.5.2 题目内容:

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
4.5.3 题目示例：

示例 1：
 
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
 
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
4.5.4 求解代码：

public static int lengthOfLIS(int[] nums) {
		if(nums.length == 0)
			return 0;
	    int ans = 1;
	    int[] dp = new int[nums.length];
	    dp[0] = 1;
	    
	    for(int i=1;i
	    	dp[i] = 1;
	    	for(int j=0;j
	    		if(nums[i] > nums[j]) {
	    			dp[i] = Math.max(dp[i], dp[j] + 1);
	    		}
	    	}
	    	ans = Math.max(ans, dp[i]);
	    }
		return ans;
	}

4.5.5 官方题解

---

4.6 Z字形变换

4.6.1 题目来源: LeetCode_Z字形变换

4.6.2 题目内容:

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
 
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

4.6.3 题目示例：

示例 1：
输入：s = “PAYPALISHIRING”, numRows = 4
输出：“PINALSIGYAHRPI”
解释：
P    I         N
A     L S      I  G
Y A   H R
P       I

4.6.4 求解代码：

	
	public static String convert(String s, int numRows) {
		int n = s.length(), r = numRows;
		if (r == 1 || r >= n) {
			return s;
		}
		int t = r * 2 - 2;
		
		int c = (n / t + 1) * (r - 1); 
		char[][] mat = new char[r][c];
		for (int i = 0, x = 0, y = 0; i < n; ++i) {
			mat[x][y] = s.charAt(i); 
			if (i % t < r - 1) { //因为是先赋值后判断,所以判断次数要减一次
				++x; // 向下移动
			} else {
				--x;
				++y; // 向右上移动
			}
		}
		StringBuffer ans = new StringBuffer();
		for (char[] row : mat) {
			for (char ch : row) {
				if (ch != 0) {
					ans.append(ch);
				}
			}
		}
		return ans.toString();
	}
	
	
	public static String compressionMatrix(String s,int numRows) {
		StringBuffer ans = new StringBuffer();
		int n = s.length(), r = numRows;
		if (r == 1 || r >= n) {
			return s;
		}
		
		StringBuffer[] mat = new StringBuffer[r]; //构造出葫芦藤
		
		for(int i=0;i
			mat[i] = new StringBuffer(); //构造葫芦藤下面挂的葫芦
		}
		
		for(int i=0,x=0,t = 2*r-2;i
			mat[x].append(s.charAt(i));
			if(i % t < r-1)  // x 控制该往哪行添加
				x++;
			else
				x--;
		}
		
		for(StringBuffer row: mat)
			ans.append(row);
		
		return ans.toString();
	}

4.6.5 题目思路

• 采用二维矩阵进行模拟填充会发现其具有周期性，推导出其每个周期内包含的个数为: t = 2 * numRows - 2。用（x,y）坐标刻画其移动轨迹，当 i % t < numRows 时是向下移动，否则向右上方，同时 y 值只增（需要注意编写时是先判断后变值，注意临界条件）
• 采用压缩矩阵算法，只需用 x 表示在哪行就行了。然后依次往里添加即可。

4.6.6 官方题解

---