使用定义的算法在文本中搜索潜台词

Question

我想创建一个程序来搜索文本中的潜台词。

例如，我有这个文本：abcdeabbdfeg

我想在该文本中找到：cd

但是我想用这个算法：

start = 1
end = string length of the text
middle = (start + end) / 2
if (pattern < text[middle])  end = mid - 1;
if (pattern > text[middle]) start = mid + 1;
...and continue until the pattern is found in the text

所以，我已经有了一个简单的程序，完全没有问题，但没有上面的算法，所以现在我只想在我的程序中实现上面的算法，我试了很多方法，但我的程序不会'在我添加该算法之后无论如何都不会显示任何内容...

这是我拥有并有效的代码：

void search(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    for (int i = 0; i <= N - M; i++)
    {
        int j;

        for (j = 0; j < M; j++)
        {
            if (txt[i+j] != pat[j])
                break;
        }
        if (j == M)
        {
           printf("Pattern found at index %d \n", i);
        }
    }
}

这是上面的算法实现代码：

int _tmain(int argc, _TCHAR* argv[])
{
    char t[32];
    cout << "Please enter your text (t):";
    cin >> t;

    char p[32];
    cout << "Please enter the pattern (p) you wish to look for in that text (t):";
    cin >> p;


    int start, end = 0;
    double middle = 0;
    start = 1;
    end = strlen(t);


        while (start <= end)
        {
            int M = strlen(p);
            int N = strlen(t);


            middle = std::ceil((start + end) / 2.0);
            int mid = (int)middle;
            for (int i = mid; i <= M; i++)
            {

                int j;


                for (j = 0; j < M; j++)
                {
                    if (t[mid] != p[j]) break;
                    if (p[j] < t[mid])  { end = mid - 1; }
                    else if (p[j] > t[mid]) { start = mid + 1; }
                }


                if (j == M)
                {
                    printf("Pattern found at index %d \n", i);
                }
            }
        }
        if (start > end) cout << "Search has ended: pattern p does not occur in the text." << endl;


    return 0;
}

Answer 1

你的算法还是二分查找。您将数组分成两个分区，然后select一个分区，基于字母的值。

分区搜索的要求是有一个有序的集合。

让我们用你的例子。

  0   1   2   3   4   5   6   7   8  9   10  11  
+---+---+---+---+---+---+---+---+---+---+---+---+  
| a | b | c | d | e | a | b | b | d | f | e | g |  
+---+---+---+---+---+---+---+---+---+---+---+---+

如果您选择索引 5 处的中点，则会生成字母 a。由于您首先搜索字母 c，然后搜索 d，因此算法表明字母 c 必须位于分区 6..11 中。因此，您的问题的基础。

算法将找不到cd，因为分区6..11中没有c。

该算法假定数组已排序，并且对于任何给定的索引，将有一个分区包含小于数组[index] 的值，一个分区包含大于数组[index] 的值。

您的以下代码证明了这一假设：

            if (p[j] < t[mid])  { end = mid - 1; }
            else if (p[j] > t[mid]) { start = mid + 1; }

无论您如何命名您的算法，如果它假定对数组进行排序（例如 p[j] < t[mid]），则必须对 数组进行排序。

你的数据没有排序，所以你的算法不符合假设，因此算法失败。

编辑 1：

使用分区

如果您真的必须使用分区算法，您将需要构建一组分区。
例如，一个分区从索引 0 开始，一直进行到 array[i] > array[i+1]，这在索引 4 处结束。另一个分区是 5..11。

（顺便说一句，通过确定分区，你使用了比线性搜索更多的操作。）

此时，您如何知道选择哪个分区？

你不知道。您要搜索的字母 c 位于第一个分区中的 a 和 e 之间；第二个分区中的 a 到 g。选择一个分区。如果在分区中找不到，则必须搜索其他分区。

通过对任一分区执行二分搜索，您使用的操作比线性搜索多。

使用定义的算法在文本中搜索潜台词

Search For Subtext In Text With A Defined Algorithm

c++

search

使用分区