我建议你使用一个贪婪的策略：

• 在字典中查找与不间断字符串匹配的最长单词。
• 重复直到你到达终点。
• 如果找不到匹配项，请备份并使用下一个较短的匹配项。如果没有更短的匹配项，请备份另一个步骤。

注意：这将找到一个解决方案（如果存在的话）。可能有不止一个，正如@ikegami在评论中指出的那样。

解决方案可以是只检查字典中的第一个字母。如果当前检查从下一个字母开始的下一组单词，如果找到所有字母，则打印它。然后再次开始与字典中匹配的较大元素的过程，并满足整个内容来自字典。因此所有组合都可以排序。

如果你试图从idontknowwhatto得到I don't know what to，有效的方法类似于求解longest common substring problem的动态规划方法。更具体地说，下面是有效的算法：

#!/usr/bin/perl

use utf8;
use open ':std', ':encoding(UTF-8)';
use strict;
use warnings;
use feature qw( say );

use Algorithm::Loops qw( NestedLoops );

my $dict_qfn = '/usr/share/dict/words';

sub add :lvalue {
   my $p = \shift;
   $p = \( $$p->{$_} ) for @_;
   $$p
}

my $trie;
{
   open(my $fh, '<', $dict_qfn)
      or die("Can't open dictionary \"$dict_qfn\": $!\n");

   while (my $word = <$fh>) {
      chomp($word);
      my @key = split(//, lc( $word =~ s/\PL//gr ));
      push @{ add($trie, @key, '') }, $word;
   }
}

for my $phrase (@ARGV) {
   say("$phrase:");

   my @key = split(//, lc( $phrase =~ s/\PL//gr ));

   my @results = map { [] } 0..$#key;
   {
      my @tries = ( $trie ) x (@key+1);
      for my $i (1..@key) {
         for my $j (reverse $i..@key) {
            for my $trie ($tries[$j]) {
               $trie = $tries[$j-1]
                  or next;

               $trie = $trie{ $key[$j-1] }
                  or next;

               if ( my $word_group = $trie->{''} ) {
                  push @{ $results[$j-1] }, [ $i, $word_group ];
               }
            }
         }

         $tries[$i-1] = undef;
      }
   }

   {
      my @todo = [ 0+@key ];
      while (@todo) {
         my ($i, @word_groups) = @{ shift(@todo) };
         if ($i) {
            for (@{ $results[$i-1] }) {
               my ($len, $word_group) = @$_;
               push @todo, [ $i-$len, $word_group, @word_groups ];
            }
         } else {
            my $iter = NestedLoops(\@word_groups);
            while (my @words = $iter->()) {
               say(join(" ", @words));
            }
         }
      }
   }

   say("");
}

我将把用C实现算法的工作留给您。