数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中最长的快乐前缀
假设我们有一个字符串s，我们需要找到s最长的快乐前缀。如果一个非空前缀也是一个后缀（自身除外），则称该字符串为快乐前缀。如果没有这样的快乐前缀，则返回空字符串。
例如，如果输入是“madam”，则输出将是“m”。它有4个前缀（自身除外）：“m”、“ma”、“mad”、“mada”，以及4个后缀：“m”、“am”、“dam”、“adam”。最大的既是前缀又是后缀的前缀是“m”。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数lps()，它将接收s作为参数。
n := s的长度
定义一个大小为n的数组ret
j := 0, i := 1
当i < n时，执行：
如果s[i]与s[j]相同，则
ret[i] := j + 1
(i加1)
(j加1)
否则，如果s[i]与s[j]不同，则：
如果j > 0，则：
j := ret[j - 1]
否则
(i加1)
返回ret
在主方法中执行以下操作：
n := s的长度
如果n等于1，则：
返回空字符串
定义一个数组v = lps(s)
x := v[n - 1]
ret := 空字符串
初始化i := 0，当i < x时，更新(i加1)，执行：
ret := ret + s[i]
返回ret
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <int> lps(string s){
int n = s.size();
vector<int> ret(n);
int j = 0;
int i = 1;
while (i < n) {
if (s[i] == s[j]) {
ret[i] = j + 1;
i++;
j++;
}
else if (s[i] != s[j]) {
if (j > 0)
j = ret[j - 1];
else {
i++;
}
}
}
return ret;
}
string longestPrefix(string s) {
int n = s.size();
if (n == 1)
return "";
vector<int> v = lps(s);
int x = v[n - 1];
string ret = "";
for (int i = 0; i < x; i++) {
ret += s[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestPrefix("madam"));
}输入
"madam"
输出
m
更新于：2020年6月9日
878 次浏览
广告