आम तौर पर इस प्रकार की समस्याओं को Tries का उपयोग करके हल किया जाता है। मैं How to create a trie in c# पर ट्री के कार्यान्वयन का आधार रखूंगा (लेकिन ध्यान दें कि मैंने इसे फिर से लिखा है)।
var trie = new Trie(new[] { "un", "que", "stio", "na", "ble", "qu", "es", "ti", "onable", "o", "nable" });
//var trie = new Trie(new[] { "u", "n", "q", "u", "e", "s", "t", "i", "o", "n", "a", "b", "l", "e", "un", "qu", "es", "ti", "on", "ab", "le", "nq", "ue", "st", "io", "na", "bl", "unq", "ues", "tio", "nab", "nqu", "est", "ion", "abl", "que", "stio", "nab" });
var word = "unquestionable";
var parts = new List<List<string>>();
Split(word, 0, trie, trie.Root, new List<string>(), parts);
//
public static void Split(string word, int index, Trie trie, TrieNode node, List<string> currentParts, List<List<string>> parts)
{
// Found a syllable. We have to split: one way we take that syllable and continue from it (and it's done in this if).
// Another way we ignore this possible syllable and we continue searching for a longer word (done after the if)
if (node.IsTerminal)
{
// Add the syllable to the current list of syllables
currentParts.Add(node.Word);
// "covered" the word with syllables
if (index == word.Length)
{
// Here we make a copy of the parts of the word. This because the currentParts list is a "working" list and is modified every time.
parts.Add(new List<string>(currentParts));
}
else
{
// There are remaining letters in the word. We restart the scan for more syllables, restarting from the root.
Split(word, index, trie, trie.Root, currentParts, parts);
}
// Remove the syllable from the current list of syllables
currentParts.RemoveAt(currentParts.Count - 1);
}
// We have covered all the word with letters. No more work to do in this subiteration
if (index == word.Length)
{
return;
}
// Here we try to find the edge corresponding to the current character
TrieNode nextNode;
if (!node.Edges.TryGetValue(word[index], out nextNode))
{
return;
}
Split(word, index + 1, trie, nextNode, currentParts, parts);
}
public class Trie
{
public readonly TrieNode Root = new TrieNode();
public Trie()
{
}
public Trie(IEnumerable<string> words)
{
this.AddRange(words);
}
public void Add(string word)
{
var currentNode = this.Root;
foreach (char ch in word)
{
TrieNode nextNode;
if (!currentNode.Edges.TryGetValue(ch, out nextNode))
{
nextNode = new TrieNode();
currentNode.Edges[ch] = nextNode;
}
currentNode = nextNode;
}
currentNode.Word = word;
}
public void AddRange(IEnumerable<string> words)
{
foreach (var word in words)
{
this.Add(word);
}
}
}
public class TrieNode
{
public readonly Dictionary<char, TrieNode> Edges = new Dictionary<char, TrieNode>();
public string Word { get; set; }
public bool IsTerminal
{
get
{
return this.Word != null;
}
}
}
word स्ट्रिंग आप रुचि रखते parts, में संभव अक्षरों की सूचियों की सूची में शामिल होंगे (यह शायद यह एक List<string[]> बनाने के लिए सही होगा रहे है, लेकिन यह parts.Add(new List<string>(currentParts)); की यह करने के लिए काफी आसान है। इसके बजाय parts.Add(currentParts.ToArray()); लिख सकते हैं और सभी List<List<string>>List<string[]> लिए बदल जाते हैं।
मैं Enigmativity प्रतिक्रिया का एक प्रकार जोड़ देंगे thas theretically तेजी से उसकी तुलना में है, क्योंकि यह गलत अक्षरों तुरंत बजाय बाद छानने उन्हें बाद में। आप इसे पसंद करते हैं, तो आपको चाहिए की निरस्त कर देती है उसे एक +1 दें, क्योंकि उसके विचार के बिना, यह भिन्न है टी संभव नहीं होगा। लेकिन ध्यान दें कि यह अभी भी एक हैक है।
from n in Enumerable.Range(1, t.Length - 1)
let s = t.Substring(0, n)
where isSyllable(s)
हम की लंबाई के लंबाई 1 से एक शब्द के सभी संभव अक्षरों, गणना: "सही" समाधान Trie (रों) एक व्याख्या का उपयोग कर :-)
Func<string, bool> isSyllable = t => Regex.IsMatch(t, "^(un|que|stio|na|ble|qu|es|ti|onable|o|nable)$");
Func<string, IEnumerable<string[]>> splitter = null;
splitter =
t =>
(
from n in Enumerable.Range(1, t.Length - 1)
let s = t.Substring(0, n)
where isSyllable(s)
let e = t.Substring(n)
let f = splitter(e)
from g in f
select (new[] { s }).Concat(g).ToArray()
)
.Concat(isSyllable(t) ? new[] { new string[] { t } } : new string[0][]);
var parts = splitter(word).ToList();
में है शब्द -1 और जांचें कि यह एक अक्षर है या नहीं। हमने सीधे गैर-अक्षरों को बुझाया। एक अक्षर के रूप में पूरा शब्द बाद में जांच की जाएगी।
let e = t.Substring(n)
let f = splitter(e)
हम स्ट्रिंग
from g in f
select (new[] { s }).Concat(g).ToArray()
के शेष भाग के अक्षरों खोज और हम "वर्तमान" शब्दांश के साथ पाया अक्षरों श्रृंखला। ध्यान दें कि हम कई बेकार सरणी बना रहे हैं। अगर हम परिणाम के रूप में IEnumerable<IEnumerable<string>> स्वीकार करते हैं, तो हम इसे ToArray निकाल सकते हैं।
(हम कई कतारें लग पुनर्लेखन कर सकता है, जैसे
from g in splitter(t.Substring(n))
select (new[] { s }).Concat(g).ToArray()
, कई let को हटाने, लेकिन हम स्पष्टता के लिए यह काम नहीं चलेगा)
और हमने पाया अक्षरों के साथ "वर्तमान" शब्दांश श्रेणीबद्ध ।
.Concat(isSyllable(t) ? new[] { new string[] { t } } : new string[0][]);
यहाँ हम क्वेरी पुनर्निर्माण एक छोटे से इतना को यह Concat का उपयोग नहीं और खाली सरणियों बना सकते हैं, लेकिन यह होगा एक छोटे से जटिल
में (हम एक isSyllable(t) ? new[] { new string[] { t } }.Concat(oldLambdaFunction) : oldLambdaFunction के रूप में पूरे लैम्ब्डा समारोह को फिर से लिखने सकता है) अंत, यदि पूरा शब्द एक अक्षर है, तो हम पूरे शब्द को एक अक्षर के रूप में जोड़ते हैं।
var word = "misunderstand";
Func<string, bool> isSyllable =
t => Regex.IsMatch(t, "^(mis|und|un|der|er|stand)$");
var query =
from i in Enumerable.Range(0, word.Length)
from l in Enumerable.Range(1, word.Length - i)
let part = word.Substring(i, l)
where isSyllable(part)
select part;
यह रिटर्न: अन्यथा हम एक खाली सरणी (ताकि कोई Concat)
आपको अपने अक्षरों को सूचीबद्ध करने के लिए ट्री का उपयोग करना चाहिए। या आप नाइवर समाधान का उपयोग कर सकते हैं :-) – xanatos