如何用C++判断一个字符串是否是另一个字符串的子串 |21xrx.com

如何用C++判断一个字符串是否是另一个字符串的子串

2023-07-12 05:44:04 深夜i -- --

C++ 判断字符串子串

在编程中，经常会遇到需要判断一个字符串是否是另一个字符串的子串的情况。本文将介绍如何使用C++语言来实现这一功能。

方法一：暴力匹配法

暴力匹配法也叫朴素匹配法，即通过穷举的方式，将要匹配的字符串与目标字符串的每一个子串进行比较，如果匹配成功，就返回匹配的起始位置，否则继续匹配下一个子串，直到匹配成功或者匹配完所有子串。

以下是该方法的代码实现：


#include <iostream>
#include <cstring>
using namespace std;
int findSubStr(char *s1, char *s2) {
  int len1 = strlen(s1);
  int len2 = strlen(s2);
  if (len1 < len2)
    return -1;
  
  for (int i = 0; i <= len1 - len2; i++) { // 枚举起始位置
    int j = 0;
    while (j < len2 && s1[i + j] == s2[j]) { // 逐个比较
      j++;
    }
    if (j == len2)  // 匹配成功
      return i;
    
  }
  return -1; // 匹配失败
}
int main() {
  char s1[100], s2[100];
  cin >> s1 >> s2;
  int pos = findSubStr(s1, s2);
  if (pos == -1)
    cout << "not found" << endl;
   else
    cout << "found at position " << pos << endl;
  
  return 0;
}

方法二：KMP算法

KMP算法是一种更加高效的字符串匹配算法，它利用了已知信息来尽可能地减少匹配次数。具体实现过程如下：

1. 构建next数组。next数组表示在目标字符串中，当匹配到某个字符时，如果这个字符匹配失败，应该将模式串向右移动多少个位置。

2. 使用next数组进行匹配。具体实现方法是在匹配过程中，如果匹配失败，则根据next数组来计算模式串应该向右移动多少个位置，从而减少匹配次数。

以下是该方法的代码实现：


#include <iostream>
#include <cstring>
using namespace std;
void getNext(char *s, int next[]) {
  int len = strlen(s);
  next[0] = next[1] = 0;
  for (int i = 1, j = 0; i < len; i++) {
    while (j > 0 && s[i] != s[j]) {
      j = next[j];
    }
    if (s[i] == s[j]) {
      j++;
    }
    next[i + 1] = j;
  }
}
int KMP(char *s1, char *s2) {
  int len1 = strlen(s1);
  int len2 = strlen(s2);
  int next[100];
  getNext(s2, next);
  for (int i = 0, j = 0; i < len1; i++) {
    while (j > 0 && s1[i] != s2[j]) {
      j = next[j];
    }
    if (s1[i] == s2[j]) {
      j++;
    }
    if (j == len2) {
      return i - len2 + 1;
    }
  }
  return -1;
}
int main() {
  char s1[100], s2[100];
  cin >> s1 >> s2;
  int pos = KMP(s1, s2);
  if (pos == -1)
    cout << "not found" << endl;
   else
    cout << "found at position " << pos << endl;
  
  return 0;
}

综上所述，以上两种方法均可以用C++来判断一个字符串是否是另一个字符串的子串，其中KMP算法具有更高效的特点，适合对性能要求更高的场合。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++的回调函数中使用全局变量

评论区

()

相似文章