数据结构(c++)字符串 模式匹配算法问题,对高手来说只要写一点点_百度...

发布网友 发布时间：2022-04-25 03:17

我来回答

共3个回答

热心网友 时间：2022-04-19 04:20

#include <string>
using namespace std;

string s = "zabcdefg";

int index1(const string ss, int pos)
{
if (pos<0 || pos>s.length())
printf("pos²»ºÏ·¨£¡");
int i = pos, j = 0;

while (i < s.length() && j < ss.length()) {
if (s[i]==ss[j]) {
i++;
j++;
} else {
i=i-j+1;
j=0;
}
}

if (j>=ss.length())
return (i-j+1);
else
return -1;
}
void getnext(const string ss, int *next)
{
int i = 0, j = -1;
next[i] = -1;
while (i < ss.length()) {
if (j == -1 || s[i] == ss[j]) {
i++;
j++;
next[i]=j;
} else
j = next[j];
}
}

int index2(const string ss, int pos)
{
int *next = new int[ss.length()];
getnext(ss, next);

int i = pos, j = 0;
while (i < s.length() && j < ss.length()) {
if (j==0 || s[i]==ss[j] ) {
++i;
++j;
} else {
j = next[j];
}
}

if (j >= ss.length())
return i-ss.length()+1;
else
return -1;
}

int main()
{
string ss = "abc";
printf("index1: %d, index2: %d\n", index1(ss, 0), index2(ss, 0));

return 0;
}

热心网友 时间：2022-04-19 05:38

唉，还是去CSDN问吧，百度知道太水了，都是些弱智题。以后不来了。。

热心网友 时间：2022-04-19 07:13

恩,百度提问太差了 我都丢了几次高分都没有成功!
我估计丢了500分了不是乱答就是没通过,分又没有