結果
問題 | No.599 回文かい |
ユーザー |
![]() |
提出日時 | 2017-11-25 15:09:34 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 223 ms / 4,000 ms |
コード長 | 1,075 bytes |
コンパイル時間 | 610 ms |
コンパイル使用メモリ | 97,492 KB |
実行使用メモリ | 110,992 KB |
最終ジャッジ日時 | 2024-06-12 22:40:38 |
合計ジャッジ時間 | 1,943 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
void main(){ import std.stdio, std.string, std.conv, std.algorithm; auto s=readln.chomp.to!(char[]); int[] zAlgorithm(char[] _s){ auto _n=to!(int)(_s.length); auto z=new int[](_n); if(_n==0) return z; z[0]=_n; int _i=1, _j=0; // s[0, j), s[i, i+j) while(_i<_n){ while(_i+_j<_n && _s[_j]==_s[_i+_j]) _j++; z[_i]=_j; if(_j==0){_i++; continue;} auto k=1; while(_i+k<_n && k+z[k]<_j) z[_i+k]=z[k], k++; // s[k, k+z[k]) in s[k, j) _i+=k; _j-=k; // s[0, j-k) == s[i+k, j) } return z; } auto mm=new long[](s.length/2+1); fill(mm, -1); const long mod=1_000_000_000+7; long fun(int i){ if(mm[i]>=0) return mm[i]; auto t=s[i..($-i)]; long ret=1; auto z=zAlgorithm(t); for(int j=1; j<=(t.length/2); j++){ if(j==z[$-j]) (ret+=fun(i+j))%=mod; } return mm[i]=ret; } writeln(fun(0)); } void rd(T...)(ref T x){ import std.stdio, std.string, std.conv; auto l=readln.split; assert(l.length==x.length); foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } }