結果
問題 | No.599 回文かい |
ユーザー |
|
提出日時 | 2017-11-24 22:46:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 4,000 ms |
コード長 | 1,511 bytes |
コンパイル時間 | 972 ms |
コンパイル使用メモリ | 105,224 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 07:37:25 |
合計ジャッジ時間 | 2,126 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>using namespace std;void ZAlgorithm(const string& s, vector<int>& len){int n = s.size();len.resize(n);if(n == 0)return;int i = 1;int j = 0;len[0] = n;while(i < n){while(i+j < n && s[j] == s[i+j])++j;len[i] = j;if(j == 0){++ i;continue;}int k = 1;while (i+k < n && k+len[k] < j){len[i+k] = len[k];++ k;}i += k;j -= k;}}const int MOD = 1000000007;int main(){string s;cin >> s;int n = s.size();int ans = 0;vector<int> dp(n/2+1, 0);dp[0] = 1;for(int i=0; i<n/2+1; ++i){ans += dp[i];ans %= MOD;int m = n - 2 * i;string t = s.substr(i, m);vector<int> len;ZAlgorithm(t, len);for(int j=0; j<m/2; ++j){if(len[m-1-j] == j + 1){dp[i+j+1] += dp[i];dp[i+j+1] %= MOD;}}}cout << ans << endl;return 0;}