小编Pri*_*shC的帖子

刚刚学习了最常见的子串算法,我对这个问题的特定变体感到好奇.它描述如下 - :

给定两个非空的字符串序列,X =(x1,x2,x3,....,x(n))和Y =(y1,y2,y3,...,y(m)),其中x (i)和y(i)是字符串,找到X中最长的字符串,它是Y 的所有字符串的子字符串.

我有一个函数substring(x, y)返回布尔值,描述x是否是y中的子串.显然,我必须连接Y中的所有字符串以形成一个大字符串,比如用B表示.我想到了以下方法 - :

• 天真:首先连接X中的所有字符串以形成字符串A(n).应用子串(A(n),B) - 这包括在字符串A(n)中向后迭代.如果为true,则算法在此结束并返回A(n) - 或者其中包含的任何部分包含在所述子字符串中.如果没有,继续申请(A(n - 1),B)等.如果X中不存在这样的字符串,则返回空字符串.

显然,这种方法会占用相当多的运行时间,具体取决于实现方式.假设我使用迭代方法,在每次迭代时,我将不得不在该级别/索引处向后迭代String,然后应用substring().这将需要至少两个循环,O(size(B) * maxlength(x1, x2,...))最坏的情况时间,或更多取决于substring()(纠正我,如果错误).

我想到了基于后缀树/数组的第二种方法.

• 广义后缀树:我使用O(maxlength(y1, y2,...)(？)中的Ukkonen算法构建序列Y的GST .我对后缀树木缺乏了解.我相信后缀树方法会大大减少查找子字符串的运行时间(以空间为代价),但我不知道如何实现该操作.

如果有更好的方法,我很想知道.

编辑:道歉,如果我似乎放弃了这个话题.

如果我不使用GST,而是使用一些标准数据结构,例如堆栈,队列,集合,堆,优先级队列等,该怎么办？序列X必须先排序,最大的字符串首先是自然的.如果我将它存储在字符串数组中,我将不得不使用诸如mergesort/quicksort之类的排序算法.目标是尽可能获得最有效的运行时间.

我是否可以将X存储在一个自动对其元素进行排序的结构中？最大堆怎么样？

看起来后缀树似乎是以这种方式查找子串的最佳方式.我可以使用其他任何数据结构吗？

我们有G = (V, E)一个comm的有向图.每个边缘具有不失败概率r(u, v)(定义为边缘权重)的网络,其位于区间[0,1]中.概率是独立的,因此从一个顶点到另一个顶点,如果我们乘以所有概率,我们得到整个路径没有失败的概率.

我需要一个有效的算法来找到其他给定的顶点,从一个给定的顶点最可靠的路径(即从第一个顶点到第二路径,该路径是最可能失败).我知道这log(r · s) = log r + log s会有所帮助.

这是我到目前为止 - :

DIJKSTRA-VARIANT (G, s, t)
for v in V:
    val[v] ? ?
A ? ?
Q ? V to initialize Q with vertices in V.
val[s] ? 0
while Q is not ? and t is not in A
    do x ? EXTRACT-MIN (Q)
    A ? A ? {x}
    for each vertex y ? Adj[x]
        do if val[x] …

正如标题所示,我试图以编程方式模拟MessageBox中的按钮单击.我之前尝试通过其标题找到其句柄,并应用WM_CLOSE或SC_CLOSE在中关闭MessageBox SendMessage().但是,由于存在"是/否"按钮,这不起作用(X按钮呈灰色显示).

现在我想点击No按钮,如下所示 - :

List<IntPtr> result = new List<IntPtr>();
GCHandle listHandle = GCHandle.Alloc(result);
try
{
     IntPtr Window_hWnd = CloseMessageBox.FindWindowByCaption("#32770", "LastQuestion"); //Could use null as the first argument too. "#32770" represents classname Dialog.
     CloseMessageBox.EnumChildWindows(Window_hWnd, (hWnd, lParam) =>
     {
          StringBuilder sb = new StringBuilder();
          foreach (var control in GCHandle.FromIntPtr(lParam).Target as List<IntPtr>)
          {
                CloseMessageBox.GetWindowText(control, sb, 250);
                if (sb.Equals("&No"))
                {
                    CloseMessageBox.PostMessage(hWnd, CloseMessageBox.MouseDown, 0, 0);
                    CloseMessageBox.PostMessage(hWnd, CloseMessageBox.MouseUp, 0, 0);
                }
          }
          return false;
     }, GCHandle.ToIntPtr(listHandle));

 }
 catch (Exception e) …