fork download
copy 
  1.  
  2. size_t[string][string] memoAAs;
  3. string[] targetInfixes;
  4.  
  5. size_t[string] count(const string from) @safe {
  6.     size_t[string] aa;
  7.     if (from in memoAAs) {
  8.         return memoAAs[from];
  9.     } else if (from.length <= 1) {
  10.         foreach (inf; targetInfixes)
  11.             aa[inf] = 0;
  12.         aa[""] = 1;
  13.         aa[from] = 1;
  14.     } else {
  15.         const auto f = count(from[0..($/2)]);
  16.         const auto l = count(from[($/2)..$]);
  17.         foreach (inf; targetInfixes) {
  18.             aa[inf] = 0;
  19.             for (size_t i = 0; i <= inf.length; ++i) {
  20.                 aa[inf] += f[inf[0..i]] * l[inf[i..$]];
  21.             }
  22.         }
  23.     }
  24.     memoAAs[from] = aa;
  25.     return aa;
  26. }
  27.  
  28. string[] infixes(string s) @safe {
  29.     import std.array;
  30.     auto a = appender!(string[]);
  31.     size_t i = 0;
  32.     size_t e = 0;
  33.     while (i != s.length) {
  34.         a.put(s[i..e]);
  35.         if (e == s.length){
  36.             ++i; e = i + 1;
  37.         } else {
  38.             ++e;
  39.         }
  40.     }
  41.     return a.data;
  42. }
  43.  
  44. void main() @safe {
  45.     import std.stdio : writeln;
  46.     import std.utf : toUTF8;
  47.     import std.range : join, repeat;
  48.  
  49.     auto odai = "odai";
  50.     auto ss = [ "odadai", "odaiodai", "ooooddddaaaaiiii", "daioadiao" ];
  51.     targetInfixes = infixes(odai);
  52.  
  53.     foreach (s; ss) {
  54.         string t = s.repeat(1000).join.toUTF8;
  55.         writeln(count(t)[odai]);
  56.     }
  57. }
  58.  
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
167501334000
668668500500
10730784064000
999666166500
https://ideone.com/lhlPdj
language:
D (dmd 2.085.0)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!