从n个连续的固定长度子串重建一个字符串
我有一个 n+2 个长度为 3 的连续子串的列表作为输入。 我的目标是找出是否存在一个长度为 n 的字符串，使得它的所有长度为 2 的连续子串正是我给出的输入列表。
我怎样才能有效地解决这个问题（例如长度为4000的字符串）？
我尝试过一种类似于矩阵链乘法的 DP 方法，但它不起作用。
现在我想我可以将这个问题转换成一个图，其中子串是顶点，并且如果子串可以连接成长度为4的子串（例如abc和bcd），则两个顶点（长度为3的子串）通过边连接是相连的，因为它们可以连接成 abcd）。尝试在此图中找到欧拉路径可以解决我的问题吗？还是我对这一切的看法完全错误？
I have as input a list of n+2 continuous substrings of length 3.
My goal is to find out whether there exists a string of length n such that all its continuous substrings of length 2 are exactly the input list that I have been given.
How can I efficiently solve this problem (e.g. for strings of length 4000)?
I have tried out a DP approach similiar to the one used for matrix chain multiplication but it didn't work.
Now I am thinking that I could convert this problem into a graph where the substrings are the vertices and two vertices (substrings of length 3) are connected by an edge if the substrings can be joined into a substring of length 4 (e.g. abc and bcd are connected as they can be joined into abcd). Would trying to find a Eulerian path in this graph solve my problem? Or am I completely wrong about all this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论