字符串包含的算法问题(求助)
一个包含匹配的算法问题.如何实现对一个长字符串的包含组合计算,比如,输入有字符串: 123456789
在已经有的集合中有短字符串123,456,789,234,5678,12,345,789.234567.
那么完全匹配包含的字符串组合有123,456,789,(这三个字符串组成了输入的长字符串)
其余不完全匹配包含的字符串组合有3组.
234,5678.
12,345,789
234567
也就是总的可以找出4组包含集合,其中第一组包含且匹配
这样的算法如何实现,希望谁能指点一下,谢谢! --------------------编程问答-------------------- 这个问题让我想去几年前解决过的一道ACM题，用Trie来构造状态机可以做，由于这个过程中有分支，因此用Trie也只能构造NFA的状态机，需要配合状态Hash，把NFA转为DFA。当然不追求极限效率的话，在NFA里面也是可以做的，那样的话直接在Trie中搜索就行了。 --------------------编程问答-------------------- 又想了一下，如果数据不是很长的话，Trie配合一个bool[]数组记录状态，也是可以做的。 --------------------编程问答-------------------- 路过 不懂 帮顶 蹭分 --------------------编程问答--------------------
谢谢,请问你能简略说一下算法的实现过程吗,你说的这些trie,NFA,我都不是很明白.我就是感觉在寻找的过程中,可能需要循环递归并记录分支. --------------------编程问答-------------------- LZ给个大一些的测试数据吧，我写个看看，没有太多基础的话，我恐怕也讲不明白！
--------------------编程问答--------------------
我举的例子或许过于生硬,实际上我是想处理中文语句的分析,比如:
我喜欢你喜欢我.
在我们已经有的记忆中,这句话是可以不同解析的,它可以被认知为
1我 喜欢 你喜欢我
2我 喜欢 你 喜欢 我
对于小孩子来说,他可能不明白"喜欢"的意思,而仅仅只是明白"我",'你"
所以这句话就被认知为:
3: 我 你 我
上面的12是对这句话的完全解析,而3是忽略性解析,其中不认识的词语被忽略
我想实现的就是如何从一句话中提炼出符合已有认知的概念组.
3 --------------------编程问答-------------------- 听你所讲 有点中文分词的意思了 --------------------编程问答-------------------- 我用1楼的数据写了一个，临时弄的，也不知道有没有bug，lz帮着测试一下吧！
using System;
using System.Collections.Generic;
namespace HelloWorld
{
class Program
{
static void Main(string[] args)
{
string[] keywords = new string[] { "123", "456", "789", "234" , "5678", "12", "345", "789", ".234567"};
string content = "123456789";
Trie keywordTrie = new Trie();
keywordTrie.AppendRange(keywords);
int[] dp = new int[content.Length + 1];
for (int i = 1; i < dp.Length; i++)
dp[i] = -1;
for (int i = 0; i < dp.Length; i++)
{
if (dp[i] != -1)
{
TrieNode node = keywordTrie.Root;
for (int j = i; j < content.Length; j++)
{
if (node.ChildNodes.ContainsKey(content[j]))
{
node = node.ChildNodes[content[j]];
if (node.IsLeaf && dp[j + 1] == -1)
dp[j + 1] = i;
}
else
break;
}
}
}
if (dp[dp.Length - 1] == -1)
Console.WriteLine("无法构造");
else
{
int index = dp.Length - 1;
while (index != 0)
{
Console.WriteLine(content.Substring(dp[index], index - dp[index]));
index = dp[index];
}
}
Console.ReadKey();
}
}
public class TrieNode
{
private Dictionary<char, TrieNode> _childNodes = new Dictionary<char, TrieNode>();
public Dictionary<char, TrieNode> ChildNodes { get { return _childNodes; } }
public char Key;
public string Value;
public TrieNode FailNode;
public TrieNode ParentNode;
public bool IsLeaf;
public TrieNode() { }
public TrieNode(char value) { Key = value; }
public TrieNode AppendChild(char key)
{
if (!_childNodes.ContainsKey(key))
{
TrieNode node = new TrieNode(key);
node.ParentNode = this;
_childNodes.Add(key, node); ;
}
return _childNodes[key];
}
}
public class Trie
{
public TrieNode Root { get; set; }
public Trie()
{
Root = new TrieNode();
Root.ParentNode = Root;
Root.FailNode = Root;
}
public void Append(string keyword)
{
TrieNode pNode = Root;
for (int i = 0; i < keyword.Length; i++)
pNode = pNode.AppendChild(keyword[i]);
pNode.IsLeaf = true;
pNode.Value = keyword;
}
public void AppendRange(string[] keywords)
{
foreach (string item in keywords)
Append(item);
BuildFailNode();
}
public void Clear()
{
Root.ChildNodes.Clear();
}
public void BuildFailNode()
{
Queue<TrieNode> bfsQueue = new Queue<TrieNode>();
bfsQueue.Enqueue(Root);
TrieNode node, failNode;
while (bfsQueue.Count > 0)
{
node = bfsQueue.Dequeue();
failNode = node.ParentNode;
while (!failNode.Equals(Root))
{
failNode = failNode.FailNode;
if (failNode.ChildNodes.ContainsKey(node.Key))
{
failNode = failNode.ChildNodes[node.Key];
break;
}
}
node.FailNode = failNode;
foreach (TrieNode child in node.ChildNodes.Values)
bfsQueue.Enqueue(child);
}
}
}
}
--------------------编程问答-------------------- litaoye,非常感谢你的热心帮助,我的QQ是404524320,如果 你愿意,可以加个QQ,我有很多有趣的算法问题,希望可以多多交流 --------------------编程问答-------------------- 我马上测试你的算法 --------------------编程问答-------------------- 班门弄斧
--------------------编程问答-------------------- 刚回家吃了饭，多交流！我的方法也算不上多好，复杂度大概是O(n*k)的，k为平均的匹配长度，不会超过所给的最长单词的长度。想达到O(n)的话，还得转为dfa才行。
void Main()
{
string[] keywords = new string[] { "123", "456", "789", "234" , "5678", "12", "345", "789", ".234567"};
string content = "123456789";
var query=(from x in keywords
from y in keywords
from z in keywords
where x+y+z==content
select new {x,y,z}).Distinct();
query.ToList().ForEach(q=>Console.WriteLine("{0}\t{1}\t{2}",q.x,q.y,q.z));
//123 456 789
}
当然如果数据规模本身就不大的话，用我的这个方法就没什么意义了，Tim同志的方法简单易懂，思路清晰，我们大家一直都用它。
补充：.NET技术 , C#
