C++实现“最长公共前缀”算法
时间: 2023-11-02 12:06:39 浏览: 55
最长公共前缀(Longest Common Prefix,简称LCP)是指在一组字符串中,所有字符串共有的、最长的前缀子串。
C++实现LCP的一种简单方法是使用字符数组,遍历字符串数组中的每个字符串的每个字符,直到出现不同的字符或到达某个字符串的结尾。代码如下:
```c++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
int n = strs.size();
int len = strs[0].size();
for (int i = 0; i < len; i++) {
char c = strs[0][i];
for (int j = 1; j < n; j++) {
if (strs[j][i] != c || i == strs[j].size()) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
int main() {
vector<string> strs = {"flower", "flow", "flight"};
string lcp = longestCommonPrefix(strs);
cout << "Longest Common Prefix: " << lcp << endl;
return 0;
}
```
在这个示例中,我们使用了一个字符串数组`strs`来存储所有的字符串。然后我们定义一个函数`longestCommonPrefix`来计算最长公共前缀。如果字符串数组为空,我们直接返回一个空字符串。接着,我们遍历第一个字符串中的每个字符。对于每个字符,我们检查所有其他字符串在该位置上是否与它相同。如果有任何一个字符串在该位置上与第一个字符串不同,或者该字符串已经到达了某个字符串的结尾,我们就返回第一个字符串的前缀子串。如果我们遍历完了第一个字符串,那么第一个字符串就是所有字符串的最长公共前缀。
在这个示例中,我们使用了`substr`函数来截取字符串的前缀子串。如果最长公共前缀为空字符串,该函数会返回一个空字符串。