字符串作为数据结构中的基础内容，也是面试中经常会考察的基本功之一，比如实现 strcpy，strcmp等基本函数等，回文字符串，字符串搜索，正则表达式等。本文相关代码见 这里。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
1 字符串基本操作
首先来看一些字符串的基本函数的实现，以下代码取自MIT6.828课程。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
// 字符串长度
int strlen(const char *s)
{
int n;
for (n = 0; *s != '\0'; s++)
n++;
return n;
}
// 字符串复制
char *strcpy(char *dst, const char *src)
{
char *ret;
ret = dst;
while ((*dst++ = *src++) != '\0')
/* do nothing */;
return ret;
}
// 字符串拼接
char *strcat(char *dst, const char *src)
{
int len = strlen(dst);
strcpy(dst + len, src);
return dst;
}
// 字符串比较
int strcmp(const char *p, const char *q)
{
while (*p && *p == *q)
p++, q++;
return (int) ((unsigned char) *p - (unsigned char) *q);
}
// 返回字符串s中第一次出现c的位置
char *strchr(const char *s, char c)
{
for (; *s; s++)
if (*s == c)
return (char *) s;
return 0;
}
// 设置内存位置v开始的n个元素值为c
void *memset(void *v, int c, size_t n)
{
char *p;
int m;
p = v;
m = n;
while (--m >= 0)
*p++ = c;
return v;
}
// 内存拷贝，注意覆盖情况
void *memmove(void *dst, const void *src, size_t n)
{
const char *s;
char *d;
s = src;
d = dst;
if (s < d && s + n > d) {
s += n;
d += n;
while (n-- > 0)
*--d = *--s;
} else
while (n-- > 0)
*d++ = *s++;
return dst;
}
复制代码2 字符串相关面试题
2.1 最长回文子串
题： 给定一个字符串，找出该字符串的最长回文子串。回文字符串指的就是从左右两边看都一样的字符串，如aba，cddc都是回文字符串。字符串 abbacdc 存在的回文子串有 abba 和 cdc，因此它的最长回文子串为abba。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
一个容易犯的错误文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
初看这个问题可能想到这样的方法：对字符串S逆序得到新的字符串S'，再求S和S'的最长公共子串，这样求出的就是最长回文子串。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
- 如
S = caba,S' = abac，则S和S'的最长公共子串为aba，这个是正确的。 - 但是如果
S = abacdfgdcaba,S’ = abacdgfdcaba，则S和S'的最长公共子串为abacd，显然这不是回文字符串。因此这种方法是错误的。
判定一个字符串是否是回文字符串文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
要找出最长回文子串，首先要解决判断一个字符串是否是回文字符串的问题。最显而易见的方法是设定两个变量i和j，分别指向字符串首部和尾部，比较是否相等，然后 i++，j--，直到 i >= j 为止。下面的代码是判断字符串 str[i, j] 是不是回文字符串，即字符串str从i到j的这一段子串是否是回文字符串，在后面会用到这个方法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* 判断字符串s[start:end]是否是回文字符串
*/
int isPalindrome(string s, int start, int end)
{
for (; start < end; ++start,--end) {
if (s[start] != s[end])
return 0;
}
return 1;
}
复制代码解1：蛮力法求最长子串文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
蛮力法通过对字符串所有子串进行判断，如果是回文字符串，则更新最长回文的长度。因为长度为N的字符串的子串一共可能有 (1+N)*N/2 个，每次判断子串需要 O(N) 的时间，所以一共需要 O(N^3) 时间求最长回文子串。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* 最长回文子串-蛮力法 O(N^3)
*/
string longestPalindrome(string s)
{
int len = s.length(), maxLen = 1;
int start=0, i, j;
/*遍历字符串所有的子串，若子串为回文字符串则更新最长回文的长度*/
for (i = 0; i < len - 1; i++) {
for (j = i + 1; j < len; j++) {
if (isPalindrome(s, i, j)) { //如果str[i,j]是回文，则判断其长度是否大于最大值，大于则更新长度和位置
int pLen = j - i + 1;
if (pLen > maxLen) {
start = i; //更新最长回文起始位置
maxLen = pLen; //更新最长回文的长度
}
}
}
}
return s.substr(start, maxLen);
}
复制代码解2：动态规划法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
因为蛮力法判定回文的时候需要很多重复的计算，所以可以通过动态规划法来改进该算法。假定我们知道“bab”是回文，则“ababa”也一定是回文。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
定义P[i, j] = true 如果子串P[i, j]是回文字符串。
则 P[i, j] <- (P[i+1, j-1] && s[i] = s[j])。
Base Case:
P[i, i ] = true
P[i, i+1 ] = true <- s[i] = s[i+1]
复制代码据此，实现代码如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* 最长回文子串-动态规划法,该方法的时间复杂度为O(N^2)，空间复杂度为O(N^2)。
*/
/**
* 最长回文子串-动态规划法,该方法的时间复杂度为O(N^2)，空间复杂度为O(N^2)。
*
* 思想：定义P[i, j] = 1 如果子串P[i, j]是回文字符串。
* 则 P[i, j] <- (P[i+1, j-1] && s[i] == s[j])。
*
* Base Case:
* P[ i, i ] <- 1
* P[ i, i+1 ] <- s[i] == s[i+1]
*/
string longestPalindromeDP(string s)
{
int n = s.length();
int longestBegin = 0, maxLen = 1;
int **P;
int i;
/*构造二维数组P*/
P = (int **)calloc(n, sizeof(int *));
for (i = 0; i < n; i++) {
P[i] = (int *)calloc(n, sizeof(int));
}
for (i = 0; i < n; i++) {
P[i][i] = 1;
}
for (int i=0; i<n-1; i++) {
if (s[i] == s[i+1]) {
P[i][i+1] = 1;
longestBegin = i;
maxLen = 2;
}
}
/*依次求P[i][i+2]...P[i][i+n-1]等*/
int len = 3;
for (; len <= n; ++len) {
for (i = 0; i < n-len+1; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && P[i+1][j-1]) {
P[i][j] = 1;
longestBegin = i;
maxLen = len;
}
}
}
/*释放内存*/
for (i = 0; i< n; i++)
free(P[i]);
free(P);
return s.substr(longestBegin, maxLen);
}
复制代码解3：中心法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
还有一个更简单的方法可以使用 O(N^2) 时间、不需要额外的空间求最长回文子串。我们知道回文字符串是以字符串中心对称的，如 abba 以及 aba 等。一个更好的办法是从中间开始判断，因为回文字符串以字符串中心对称。一个长度为N的字符串可能的对称中心有2N-1个，至于这里为什么是2N-1而不是N个，是因为可能对称的点可能是两个字符之间，比如abba的对称点就是第一个字母b和第二个字母b的中间。据此实现代码如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* 求位置l为中心的最长回文子串的开始位置和长度
*/
void expandAroundCenter(string s, int l, int r, int *longestBegin, int *longestLen)
{
int n = s.length();
while (l>=0 && r<=n-1 && s[l]==s[r]) {
l--, r++;
}
*longestBegin = l + 1;
*longestLen = r - l - 1;
}
/**
* 最长回文子串-中心法，时间O(N^2)。
*/
string longestPalindromeCenter(string s)
{
int n = s.length();
if (n == 0)
return s;
char longestBegin = 0;
int longestLen = 1;
for (int i = 0; i < n; i++) {
int iLongestBegin, iLongestLen;
expandAroundCenter(s, i, i, &iLongestBegin, &iLongestLen); //以位置i为中心的最长回文字符串
if (iLongestLen > longestLen) {
longestLen = iLongestLen;
longestBegin = iLongestBegin;
}
expandAroundCenter(s, i, i+1, &iLongestBegin, &iLongestLen); //以i和i+1之间的位置为中心的最长回文字符串
if (iLongestLen > longestLen) {
longestLen = iLongestLen;
longestBegin = iLongestBegin;
}
}
return s.substr(longestBegin, longestLen);
}
复制代码2.2 交换排序
题： 已知一个字符数组，其中存储有R、G、B字符，要求将所有的字符按照 RGB 的顺序进行排序。比如给定一个数组为 char s[] = "RGBBRGGBGB"，则排序后应该为 RRGGGGBBBB。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
解1： 这个题目有点类似于快速排序中用到的划分数组的方法，但是这里有三个字符，因此需要调用划分方法两次，第一次以 B 划分，第二次以 G 划分，这样两次划分后就可以将原来的字符数组划分成RGB 顺序。这个方法比较自然，容易想到，代码如下。这个方法的缺点是需要遍历两遍数组。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
void swapChar(char *s, int i, int j)
{
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
/**
* 划分函数
*/
void partition(char *s, int lo, int hi, char t)
{
int m = lo-1, i;
for (i = lo; i <= hi; i++) {
if (s[i] != t) {
swapChar(s, ++m ,i);
}
}
}
/**
* RGB排序-遍历两次
*/
void rgbSortTwice(char *s)
{
int len = strlen(s);
partition(s, 0, len-1, 'G'); // 以G划分，划分完为 RBBRBBGGGG
partition(s, 0, len-1, 'B'); // 再以B划分，划分完为 RRGGGGBBBB
}
复制代码解2： 其实还有一个只需要遍历一遍数组的方法，当然该方法虽然只遍历一遍数组，但是需要交换的次数并未减少。主要是设置两个变量r和g分别指示当前R和G字符所在的位置，遍历数组。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
- 1）如果第i个位置为字符R，则与前面的指示变量r的后一个字符也就是++r处的字符交换，并++g，此时还需要判断交换后的i里面存储的字符是否是G，如果是G，则需要将其与g处的字符交换；
- 2）如果第i个位置为字符G，则将其与++g处的字符交换即可。++g指向的总是下一个应该交换G的位置，++r指向的是下一个需要交换R的位置。
- 3）如果第i个位置为字符B，则什么都不做，继续遍历。
/**
* RGB排序-遍历一次
*/
void rgbSortOnce(char *s)
{
int len = strlen(s);
int lo = 0, hi = len - 1;
int r, g, i; //++r和++g分别指向R和G交换的位置
r = g = lo - 1;
for (i = lo; i <= hi; i++) {
if (s[i] == 'R') { // 遇到R
swapChar(s, ++r, i);
++g;
if (s[i] == 'G') // 交换后的值是G，继续交换
swapChar(s, g, i);
} else if (s[i] == 'G') { // 遇到G
swapChar(s, ++g, i);
} else { // 遇到B，什么都不做
}
}
}
复制代码解3： 如果不考虑用交换的思想，可以直接统计RGB各个字符的个数，然后从头开始对数组重新赋值为RGB即可。那样简单多了，哈哈。但是如果换一个题，要求是对正数、负数、0按照一定顺序排列，那就必须用交换了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
2.3 最大滑动窗口
题： 给定一个数组A，有一个大小为w的滑动窗口，该滑动窗口从最左边滑到最后边。在该窗口中你只能看到w个数字，每次只能移动一个位置。我们的目的是找到每个窗口w个数字中的最大值，并将这些最大值存储在数组B中。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
例如数组 A = [1 3 -1 -3 5 3 6 7], 窗口大小 w = 3 。则窗口滑动过程如下所示：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
输入: 数组A和w大小
输出: 数组B，其中B[i]存储了A[i]到A[i+w-1]中w个数字的最大值。
复制代码解1：简单实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
一个最简单的想法就是每次移动都计算 w 个数字的最大值并保存起来，每次计算 w 个数字的最大值需要 O(w) 的时间，而滑动过程需要滑动 n-w+1 次，n为数组大小，因此总共的时间为 O(nw) 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/*
* 求数组最大值
*/
int maxInArray(int A[], int n)
{
int max = A[0], i;
for (i = 1; i < n; i++) {
if (A[i] > max) {
max = A[i];
}
}
return max;
}
/*
* 最大滑动窗口-简单实现
*/
void maxSlidingWindowSimple(int A[], int n, int w, int B[])
{
int i;
for (i = 0; i <= n-w; i++)
B[i] = maxInArray(A + i, w);
}
复制代码解2：最大堆解法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
第1个方法思路简单，但是时间复杂度过高，因此需要改进。可以使用一个最大堆来保存w个数字，每次插入数字时只需要 O(lgw) 的时间，从堆中取最大值只需要 O(1) 的时间(堆的平均大小约为 w)。随着窗口由左向右滑动，因此堆中有些数字会失效（因为它们不再包含在窗口中）。如果数组本身有序，则堆大小会增大到n。因为堆大小并不保持在w不变，因此该算法时间复杂度为 O(nlgn)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* 最大滑动窗口-最大堆解法
*/
void maxSlidingWindowPQ(int A[], int n, int w, int B[])
{
typedef pair<int, int> Pair;
priority_queue<Pair> Q; //优先级队列保存窗口里面的值
for (int i = 0; i < w; i++)
Q.push(Pair(A[i], i)); //构建w个元素的最大堆
for (int i = w; i < n; i++) {
Pair p = Q.top();
B[i-w] = p.first;
while (p.second <= i-w) {
Q.pop();
p = Q.top();
}
Q.push(Pair(A[i], i));
}
B[n-w] = Q.top().first;
}
复制代码解3：双向队列解法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
最大堆解法在堆中保存有冗余的元素，比如原来堆中元素为 [10 5 3]，新的元素为11，则此时堆中会保存有 [11 5 3]。其实此时我们可以清空整个队列，然后再将11加入到队列即可，即只在队列中保持 [11]。使用双向队列可以满足要求，滑动窗口的最大值总是保存在队列首部，队列里面的数据总是从大到小排列。当遇到比当前滑动窗口最大值更大的值时，则将队列清空，并将新的最大值插入到队列中。如果遇到的值比当前最大值小，则直接插入到队列尾部。每次移动的时候需要判断当前的最大值是否在有效范围，如果不在，则需要将其从队列中删除。由于每个元素最多进队和出队各一次，因此该算法时间复杂度为O(N)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* 最大滑动窗口-双向队列解法
*/
void maxSlidingWindowDQ(int A[], int n, int w, int B[])
{
deque<int> Q;
for (int i = 0; i < w; i++) {
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (int i = w; i < n; i++) {
B[i-w] = A[Q.front()];
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
while (!Q.empty() && Q.front() <= i-w)
Q.pop_front();
Q.push_back(i);
}
B[n-w] = A[Q.front()];
}
复制代码2.4 最长公共子序列
题： 给定两个序列 X = < x1, x2, ..., xm > 和 Y = < y1, y2, ..., ym >，希望找出X和Y最大长度的公共子序列(LCS)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
分析： 解决LCS的最简单的是使用蛮力法，穷举 X 的所有子序列，然后逐一检查是否是 Y 的子序列，并记录发现的最长子序列，最终取最大的子序列即可。但是 X 所有子序列有 2^m，该方法需要指数级时间，不太切实际，然而LCS问题其实具有最优子结构性质。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
LCS最优子结构:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
如 X = <A, B, C, B, D, A, B>， Y = <B, D, C, A, B, A>，则 X 和 Y 的最长公共子序列为 <B, C, B, A> 或者 <B, D, A, B>。也就是说，LCS可能存在多个。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
设 X = < x1, x2, ..., xm > 和 Y = < y1, y2, ..., yn > 为两个序列，并设 Z = < z1, z2, ..., zk > 为 X 和 Y 的任意一个LCS。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
- 如果 xm = yn，那么 zk = xm = yn，且 Zk-1 是 Xm-1 和 Yn-1 的一个LCS。
- 如果 xm != yn，那么 zk != xm，且 Z 是 Xm-1 和 Y 的一个LCS。
- 如果 xm != yn，那么 zk != yn，且 Z 是 X 和 Yn-1 的一个LCS。
因此，我们可以定义 c[i, j] 为序列 Xi 和 Yj 的一个LCS的长度，则可以得到下面的递归式：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
c[i, j] = 0 // i = 0 或者 j = 0
c[i, j] = c[i-1, j-1] + 1 // i，j > 0，且 Xi = Yj
c[i, j] = max(c[i-1, j], c[i][j-1]) // i, j > 0，且 Xi != Yj
复制代码据此可以写出如下代码求LCS的长度及LCS，使用一个辅助数组 b 存储 LCS 路径。这里给出递归算法求LCS长度，使用动态规划算法的代码见本文源码。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
/**
* LCS-递归算法
*/
#define UP 1
#define LEFT 2
#define UPLEFT 3
int lcsLengthRecur(char *X, int m, char *Y, int n, int **b)
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1]) {
b[m][n] = UPLEFT;
return lcsLengthRecur(X, m-1, Y, n-1, b) + 1;
}
int len1 = lcsLengthRecur(X, m-1, Y, n, b);
int len2 = lcsLengthRecur(X, m, Y, n-1, b);
int maxLen;
if (len1 >= len2) {
maxLen = len1;
b[m][n] = UP;
} else {
maxLen = len2;
b[m][n] = LEFT;
}
return maxLen;
}
/**
* 打印LCS，用到辅助数组b
*/
void printLCS(int **b, char *X, int i, int j)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == UPLEFT) {
printLCS(b, X, i-1, j-1);
printf("%c ", X[i-1]);
} else if (b[i][j] == UP) {
printLCS(b, X, i-1, j);
} else {
printLCS(b, X, i, j-1);
}
}
复制代码打印LCS的流程如下图所示(图取自算法导论)：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
2.5 字符串全排列
题： 给一个字符数组 char arr[] = "abc"，输出该数组中字符的全排列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
解： 使用递归来输出全排列。首先明确的是 perm(arr, k, len) 函数的功能:输出字符数组 arr 从位置 k 开始的所有排列，数组长度为 len 。基础条件是 k == len-1，此时已经到达最后一个元素，一次排列已经完成，直接输出。否则，从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换)，然后进行下一次排列，排列完成后记得恢复原来的序列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
假定数组 arr 大小 len=3，则程序调用 perm(arr, 0, 3) 可以如下理解： 第一次交换 0，0，并执行 perm(arr, 1, 3)，执行完再次交换0，0，数组此时又恢复成初始值。 第二次交换 1，0（注意数组此时是初始值），并执行 perm(arr, 1, 3), 执行完再次交换 1，0，数组此时又恢复成初始值。 第三次交换 2，0，并执行 perm(arr, 1, 3)，执行完成后交换2，0，数组恢复成初始值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
程序运行输出结果为：abc acb bac bca cba cab。即先输出以 a 为排列第一个值的排列，而后是 b 和 c 为第一个值的排列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
void perm(char *arr, int k, int len) { //k为起始位置，len为数组大小
if (k == len-1) {
printf("%s\n", arr);
return;
}
for (int i = k; i < len; i++) {
swapChar(arr, i, k); //交换
perm(arr, k+1, len); //下一次排列
swapChar(arr, i, k); //恢复原来的序列
}
}
复制代码2.6 正则表达式
题： 实现一个简易版的正则表达式，支持 ^、$、.等特性。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
正则表达式基础：一个正则表达式本身也是一个字符序列,它定义了能与之匹配的字符串集合。在 Unix/Linux 通用的正则表达式中，字符 ^ 表示字符串开始， $ 表示字符串结束。这样，^x 只能与位于字符串开始处的 x匹配， x$ 只能匹配结尾的 x，^x$只能匹配单个字符的串里的 x，而^$只能匹配空串。字符 . 能与任意字符匹配。所以，模式 x.y能匹配 xay、x2y 等等,但它不能匹配 xy 或 xaby。显然 ^.$ 能够与任何单个字符的串匹配。写在方括号 [] 里的一组字符能与这组字符中的任一个相匹配。如 [0123456789] 能与任何数字匹配。这个模式也可以简写为 [0-9]。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
解： 下面是正则表达式匹配的主函数match，接收参数为匹配模式regexp和文本text。 如果正则表达式的开头是 ^，那么正文必须从起始处与表达式的其余部分匹配。否则,我们就沿着串走下去，用 matchhere() 看正文是否能在某个位置上匹配。一旦发现了匹配,工作就完成了。注意这里 do-while的使用，有些表达式能与空字符串匹配 (例如: $ 能够在字符串的末尾与空字符串匹配，* 能匹配任意个数的字符，包括 0 个)。所以，即使遇到了空字符串，我们也还需要调用 matchhere()。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
int match(const char *regexp, const char *text)
{
if (regexp[0] == '^')
return matchhere(regexp+1, text);
do {
if (matchhere(regexp, text))
return 1;
} while (*text++ != '\0');
return 0;
}
复制代码递归函数 matchhere() 完成大部分的匹配工作：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
- 如果
regexp[0]=='\0'，表示已经匹配到末尾，则匹配成功，返回1。 - 如果表达式的最后是
$，匹配成功的条件是正文也到达了末尾，即判断*text=='\0'。如果正文text也到了末尾，则匹配成功，否则失败。 - 如果正文没有到末尾，且
regexp[0] == *text或者regexp=='.'(.表示匹配任意字符)，则递归调用matchhere继续下一次匹配。 - 如果
regexp[1]=='*'，则过程稍显复杂，例如x*。这时我们调用matchstar来处理，其第一个参数是星号的参数 (x*中的x)，随后的参数是位于星号之后的模式,以及对应的正文串。
int matchhere(const char *regexp, const char *text)
{
if (regexp[0] == '\0')
return 1;
if (regexp[0]=='$' && regexp[1]=='\0')
return *text == '\0';
if (regexp[1] == '*')
return matchstar(regexp[0], regexp+2, text);
if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
return matchhere(regexp+1, text+1);
return 0;
}
int matchstar(int c, const char *regexp, const char *text)
{
do {
if (matchhere(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
复制代码示例：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
char *regexp="abc", text="dagabcdefg"，匹配成功。char *regexp="^abc", *text="abcdefg"，匹配成功。char *regexp="^abc", *text="bcdefgabc"，匹配失败。char *regexp="abc$", *text="defghabc"，匹配成功。
2.7 KMP算法和BM算法
字符串匹配的大名鼎鼎的有KMP算法和BM算法，网上资料比较多，可以参见 grep之字符串搜索算法Boyer-Moore由浅入深（比KMP快3-5倍） 和 字符串匹配的KMP算法 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html
作者：ssjhust文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5832.html