我正在寻找PHP中最有效的算法来检查字符串是否仅由字典单词组成。
示例：
thissentencewasmadefromenglishwords
thisonecontainsyxxxyxsomegarbagexaatoo
pure
thisisalsobadxyyyaazzz
输出：
thissentencewasmadefromenglishwords
pure
a.txt
contains the dictionary words
b.txt
contains the strings: one in every line, without spaces made from a..z chars only
另一种方法是使用Aho-Corasick字符串匹配算法。基本的想法是在你的词典中阅读单词，并由此创建Aho-Corasick树结构。然后，通过搜索功能运行每个要拆分为单词的字符串。
这种方法的美妙之处在于，创建树是一次性的成本。然后，您可以将它用于正在测试的所有字符串。搜索函数以O（n）（n是字符串的长度）加上找到的匹配数运行。它真的很有效率。
搜索功能的输出将是一个字符串匹配列表，告诉您哪些单词在什么位置匹配。
维基百科的文章并没有对Aho-Corasick算法做出很好的解释。我更喜欢原始文件，它很容易接近。请参阅"高效字符串匹配：书目搜索的辅助工具"。
例如，给定你的第一个字符串：
thissentencewasmadefromenglishwords
你会得到（部分）：
this, 0
his, 1
sent, 4
ten, 7
etc.
现在，按位置对匹配列表进行排序。当你从字符串匹配器中得到它时，它将被几乎排序，但不是完全排序。
一旦列表按位置排序，您要做的第一件事就是确保在位置0处有匹配项。如果没有，则字符串未通过测试。如果存在（并且在位置0处可能有多个匹配），则获取匹配字符串的长度，并查看该位置是否存在字符串匹配。加上比赛的长度，看看下一个位置是否有比赛，等等。
如果你测试的字符串不是很长，那么你可以使用这样的暴力算法。不过，构建一个按位置索引的匹配哈希图会更有效。当然，一个特定的位置可能有多场比赛，所以你必须考虑到这一点。但是，看看在某个位置是否有比赛会很快。
当然，要实现Aho-Corasick算法还需要一些工作。快速的谷歌搜索显示有php实现可用。我不知道他们工作得有多好。
在一般情况下，这应该很快。同样，这取决于你的绳子有多长。但在任何一个位置上的比赛相对较少，这对你有帮助。您可能会构造出病态的糟糕运行时的字符串，但您可能必须非常努力地尝试。再说一遍，如果绳子很短，即使是病理性病例也不会花太长时间。
这是一个可以使用动态编程解决的问题，基于以下公式：
f(0) = true
f(i) = OR { f(i-j) AND Dictionary.contais(s.substring(i-j,i) } for each j=1,...,i
首先，将您的文件加载到字典中，然后使用DP解决方案来执行上述公式。
伪代码类似于：（希望我对索引没有"逐个关闭"。）
check(word):
f = new boolean[word.length() + 1)
f[0] = true
for i from 1 to word.length() + 1:
f[i] = false
for j from 1 to i-1:
if dictionary.contains(word.substring(j-1,i-1)) AND f[j]:
f[i] = true
return f[word.length()
我推荐一种递归方法。类似这样的东西：
<?php
$wordsToCheck = array(
'otherword',
'word1andother',
'word1',
'word1word2',
'word1word3',
'word1word2word3'
);
$wordList = array(
'word1',
'word2',
'word3'
);
$results = array();
function onlyListedWords($word, $wordList) {
if (in_array($word, $wordList)) {
return true;
} else {
$length = strlen($word);
$wordTemp = $word;
$part = '';
for ($i=0; $i < $length; $i++) {
$part .= $wordTemp[$i];
if (in_array($part, $wordList)) {
if ($i == $length - 1) {
return true;
} else {
$wordTemp = substr($wordTemp, $i + 1);
return onlyListedWords($wordTemp, $wordList);
}
}
}
}
}
foreach ($wordsToCheck as $word) {
if (onlyListedWords($word, $wordList))
$results[] = $word;
}
var_dump($results);
?>