C++实现最长公共前缀算法 |21xrx.com

C++实现最长公共前缀算法

2023-07-05 00:39:50 深夜i -- --

C++ 最长公共前缀算法

最长公共前缀是指一组字符串中，从第一个字符开始，所有字符串共同拥有的最长的前缀。例如，字符串“flower”、“flow”和“flight”中的最长公共前缀为“fl”。

在C++中，最长公共前缀算法可以通过使用字符串的基本操作和循环来实现。以下是一个简单的代码示例：


#include <iostream>
using namespace std;
string longestCommonPrefix(string arr[], int n) {
  string prefix = arr[0];
  for (int i = 1; i < n; i++) {
    string str = arr[i];
    int j = 0;
    while (j < prefix.size() && j < str.size() && prefix[j] == str[j]) {
      j++;
    }
    if (j == 0)
      return "";
    
    prefix = prefix.substr(0, j);
  }
  return prefix;
}
int main() {
  string arr[] = "flower";
  int n = sizeof(arr) / sizeof(arr[0]);
  string lcp = longestCommonPrefix(arr, n);
  cout << "The longest common prefix is: " << lcp << endl;
  return 0;
}

在上面的代码中，我们使用了一个名为longestCommonPrefix的函数来计算最长公共前缀。该函数接受一个字符串数组和一个整数n作为参数，并返回一个字符串类型的结果。

首先，我们将数组中的第一个字符串作为前缀字符串（prefix）。接下来，我们使用循环来检查数组中的所有字符串。对于每个字符串，我们使用一个while循环来逐个比较前缀字符和当前字符串中的字符，直到找到第一个不匹配的字符或者到达某个字符串的末尾。如果没有匹配的字符，则表示没有公共前缀，返回一个空字符串。

如果有匹配的字符，我们将前缀字符串更新为当前匹配的子字符串（即从第一个字符到第j个字符的子串）。最后，我们返回更新后的前缀字符串作为最终的结果。

在我们的示例中，函数将返回“fl”作为最长公共前缀。

总的来说，C++实现最长公共前缀算法是一个简单而有效的方法，可以在处理字符串相关问题时派上用场。无论是使用字符串中的基本操作语法还是利用循环来实现，都可以轻松地实现这个算法。

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

下一篇: [C++]招聘现场工程师，要求丰富项目经验！

评论区

()

相似文章