【題目鏈接】

OpenJudge NOI 1.7 34:回文子串

【題目考點】

1. 字符串

2. 枚舉

【解題思路】

假設字符串長為len，先枚舉長為2的回文子串，再枚舉長為3的回文子串，。。。，最后枚舉長為n的回文子串。
如要枚舉長為l的回文子串，先看下標0_{l-1是不是回文串，再看下標1}l是不是回文串。。。最后看下標len-l~len-1誰不是回文串。

【題解代碼】

解法1：使用字符數組

#include<bits/stdc++.h> using namespace std; char s[505]; bool isPalin(int st, int len)//s[st]開始長為len的子串是不是回文串 {//這段字符串最后一個位置為st+len-1 for(int i = st, j = st+len-1; i < j ; ++i, --j){if(s[i] != s[j])return false;}return true; } void show(int st, int len) {for(int i = st; i <= st+len-1; ++i)cout << s[i];cout << endl; } int main() {cin >> s;int len = strlen(s);for(int l = 2; l <= len; ++l)//回文子串長度 {for(int i = 0; i <= len-l; ++i)//最后一次看從len-l~len-1共l個字符是不是回文串{if(isPalin(i, l))show(i, l);} }return 0; }

解法2：使用string類

#include<bits/stdc++.h> using namespace std; string s; bool isPalin(string str)//判斷str是不是回文串 {string s1(str);//初始化s1和str相同 reverse(s1.begin(), s1.end());//將s1逆序 return str == s1;//如果逆序后和原字符串相同，那么就是回文串 } int main() {cin >> s;int len = s.length();for(int l = 2; l <= len; ++l)//回文子串長度 {for(int i = 0; i <= len-l; ++i)//最后一次看從len-l~len-1共l個字符是不是回文串{string sub = s.substr(i, l);if(isPalin(sub))cout << sub << endl;} }return 0; }

總結

以上是生活随笔為你收集整理的OpenJudge NOI 1.7 34:回文子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。