数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究不包含任何回文子串的最长子串长度
在 C++ 中，我们有预定义函数 max()，它将用于查找任何包含任何回文的最长子串。回文串是一组字符，即使在反转后也保持不变。
让我们举一个回文串的例子，以找到最长的非回文子串。
字符串malayalam本身就是一个回文，但我们需要识别最长的非回文子串。当我们将字符串malayalam（长度=9）更改为alayalam时，我们得到最长的非回文子串长度，即 8。
字符串synapse是一个非回文串，其长度为 7。
语法
程序中使用以下语法：
substr( size_a position, size_a length )
参数
size_a - 整数类型。
position - 要复制的位置的第一个字符。
Length - 子串的长度。
var_name = max( var_name, size_a length)
参数
var_name - 变量的名称。
size_a - 整数类型。
length - 子串的长度。
算法
我们将创建一个名为“isPalindrome”的全局函数，并将字符串's'作为参数传递给该函数。
在全局函数“isPalindrome”中，我们正在计算输入字符串“s”的长度并将其存储在一个名为“n”的变量中，并使用 for 循环迭代字符串字符“s”从第一个字符到中间字符。
然后，我们将创建一个 if 语句来检查“(i)-th”和“(num-i-1)-th”字符是否相等，如果它是回文则返回 false，否则返回 true。
在主函数中，我们将定义变量“str”并将输入字符串存储在其中。然后找到“str”的长度并将其存储在另一个名为“n”的变量中。
我们正在一个整数变量“answer”中存储 0，因为它将用于查找非回文子串的长度。
开始两个嵌套的for循环以迭代 str 的所有可能的子字符串。
在第二个 for 循环下使用 if 语句为每个子字符串调用上面名为“isPalindrome”的函数。
我们借助预定义函数 max（关联步骤 5）查找最长非回文子串的长度。
最后，for嵌套循环计数器将检查子字符串是非回文还是回文，然后打印非回文字符串的最长子串的长度。
示例
在此示例中，我们遵循上述算法的整个方法来学习如何查找不包含回文的最长子串的长度。
#include<iostream>
#include<algorithm>
using namespace std;
bool isPalindrome(string s) {
int n = s.length();
for (int i = 0; i < n/2; i++) {
if (s[i] != s[n-i-1]) {
return false;
}
}
return true;
}
int main() {
string str = "madam";
// “madam” string is itself a palindrome but its longest substring check so that it doesn’t become a palindrome and give its length in the output.
int n = str.length();
int answer = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j <= n; j++) {
if (!isPalindrome(str.substr(i, j-i))) {
answer = max(answer, j-i);
// return the maximum length of non-palindrome substring.
}
}
}
cout << "The length of longest substring that does not contain any palindrome: "<<answer << endl;
return 0;
}
输出
The length of longest substring that does not contain any palindrome: 4
结论
我们探讨了查找不包含任何回文的最长子串长度的概念。我们的分析观察到，可以通过将其分解成更小的子问题来解决此问题。这也是一个现实生活中的问题，在自然语言处理和生物信息学等领域具有实际应用。
258 次查看
