最常见的子串问题 [英] longest common substring problem

问题描述

hi

#include "stdafx.h"
#include "iostream"
#include <stdlib.h>
#include <string.h>
using namespace std; 
#define SIZE 100

void reset(char temp[]) //clears the array
{
for (int i=0;i <= strlen(temp);i++)
temp[i] = 0;
}

void lcs(char str1[], char str2[], char temp[], int x, int y, int i)
{
if (str1[x]==0)//end of string exit
return;
else
{
if (str1[x]==str2[y])//finds similar cells
{
temp[i]=str1[x];//copy to temp
if ((str1[x+1]!=0) && (str2[y+1]!=0))//checks that this is not the end of the strings and send 
return lcs (str1, str2, temp,x+1 ,y+1 , i+1);//the next cell to compare
}
else//the x&y are not the same
if (str2[y] == 0)//if the program finished going on the second string it reset the counter using 
return lcs (str1, str2, temp,x+1 ,strlen(temp), i+1);//temp and return the next cell from str1
if (str2[y+1] != 0)//compare x from str1 to y+1 from str2
return lcs (str1, str2, temp, x, y + 1, i);
if (str1[x] == 0)//compare x+1 from str1 to y from str2
return lcs (str1, str2, temp, strlen(temp), y, i);
}
}
void main()
{
char str1[SIZE]={0},str2[SIZE]={0},temp[SIZE]={0}, big[SIZE] = {0};//, biggest2[SIZE] = {0};
cout<<"Please enter the first string:";
cin>>str1;
cout<<"Please enter the second string:";
cin>>str2;
lcs(str1, str2, temp, 0, 0, 0);
for(int i=0;i<SIZE;i++)
	big[i]=temp[i];
reset(temp);
lcs(str2, str1, temp, 0, 0, 0);
cout<<"The longest common string is:";
if ((strlen(big)) > (strlen(temp)))
cout<<big<<endl;
else
cout<<temp;
}

以上代码返回 a ，但输入时是：

Above code returns a, but when the inputs are:

Hgaksc
Agsmcdf

它应该返回 gsc 。



请帮帮我。

我找不到它的问题

谢谢

it should return gsc.

Please help me.
I can't find it's problem
Thanks

推荐答案

gsc是最常见的子序列（不是sub-sting）。

描述和算法。

算法用C ++和其他几种语言实现。



但是如果你正在寻找最长的公共子串然后 a 是正确答案之一。

gsc is longest common sub sequence (not sub-sting).
Decription and Algorithm.
Algorithm implementation in C++ and several other languages.

But if you are looking for longest common sub-string then a is one of the correct answer.

正如CHill60所说，它根本不应该返回gsc - gsc isn两个输入的子串。

这两个输入的LCS是单个cha racter：g，s或c（如果你接受案件独立，可能是A）



Common Substring是一个短字符串出现在所有输入中的字符，而不是以相同顺序出现的字符序列，而不考虑它们之间的任何额外字符。



我建议你需要如果你想要gsc返回，那么改变你的算法是相当可观的 - 并且学习使用调试器来计算代码运行时的goign;你需要它！ ：笑：

As CHill60 says, it shouldn't return "gsc" at all - gsc isn't a substring of either input.
The LCS of those two inputs is a single character: either "g", "s", or "c" (and possibly "A" if you accept case independence)

A Common Substring is a short string of characters which appears in all the inputs, not a sequence of characters which appear in the same order without considering any extra characters between them.

I'd suggest you need to change your algorithm considerable if you want "gsc" returned - and learn to use the debugger to work out what is goign on while your code is running; you are going to need it! :laugh:

你把它命名为最长公共子串

但你的程序只是返回常用字母两个字符串。没有调试你的代码，但快速查看表明这段代码正确返回常见的字母表。

我认为你的意图是使用动态编程。请查看此页面 [ ^ ]。



如果你想找到共同点substring然后检查子字符串（任何长度）的另一种方式（数据结构）是实现后缀树。

这里 [ ^ ]是一篇关于这种方法的非常有用的文章。



另外，正如Griff建议的那样，你需要学习如何使用你的调试器。它是谷歌之后你最好的朋友:)



希望这有帮助!!

you named it as "longest common substring"
but your program is just returning the common alphabets of both the strings. Did not debug your code but a quick look suggests that this code correctly returns the common alphabets.
I think your intention is to use dynamic programming. Look at the implementation on this page[^].

If your intent is to find the common substring then another way(data structure) to check for sub string (of any length) is to implement a suffix tree.
Here[^] is a very helpful article regarding this approach.

Also as the Griff has suggested, you need to learn how to use your debugger. Its your best friend after google :)

hope this helps !!

这篇关于最常见的子串问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！