字符串与模式中的间隙匹配 [英] string matching with gaps in pattern

问题描述

假设我们允许模式P包含间隙字符◊的出现，它可以匹配任意字符串（甚至是零长度之一）。例如，模式ab◊ba◊c出现在文本cabccbacbacab

注意，间隙字符可能在模式中出现任意次数，但在文本中根本不出现。给出一个多项式时间算法来确定这样的模式P是否出现在给定的文本T中，并分析算法的运行时间。



我用google搜索但没有找到答案。我只需要了解ps uedocode。

我确实知道模式可以先转换成正则表达式，然后可以制作NFA然后需要转换为DFA ...但我不确定这是否是正确的方法？

Suppose we allow the pattern P to contain occurrences of a gap character ◊ that can match an arbitrary string of characters (even one of zero length). For example, the pattern ab◊ba◊c occurs in the text cabccbacbacab
Note that the gap character may occur an arbitrary number of times in the pattern but not at all in the text. Give a polynomial-time algorithm to determine whether such a pattern P occurs in a given text T, and analyze the running time of your algorithm.

I have googled but didnt find an answer. I only need to understand psuedocode.
I do have some idea that the pattern can be first converted into a regular expression then an NFA can be made which then need to be converted to a DFA...but I am not sure if this is the right approach?

推荐答案

我确实知道该模式可以先转换成一个正则表达式，然后可以制作NFA然后需要转换为DFA ...但我不确定这是否是正确的方法？



不 - 这不是算法，这是你的导师正在寻找的。

他没有要求实施，他正在寻找任务需要完成的基本方式，以及分析它的工作原理。



我们不打算为你做那个！

我们不做你的作业：它是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。



亲自尝试，你可能会发现它不是和你想的一样困难。

"I do have some idea that the pattern can be first converted into a regular expression then an NFA can be made which then need to be converted to a DFA...but I am not sure if this is the right approach?"

No - that's not an algorithm, which is what your tutor is looking for.
He hasn't asked for an implementation, he's looking for the underlying way that the task needs to be done, and an analysis of how well it works.

And we aren't going to do that for you!
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think.

这篇关于字符串与模式中的间隙匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！