请问如何将下面 求子串首次匹配位置,改为输出子串出现的所有位置。
#include
#include
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255
typedef cring[MAXSTRLEN+1];
Status StrAssign(SString T, char *chars)
{
int i;
if (strlen(chars) > MAXSTRLEN)
return ERROR;
else {
T[0] = strlen(chars);
for (i = 1; i <= T[0]; i++)
T[i] = *(chars + i - 1);
return OK;
}
}
void get_nextval(SString T, int nextval[])
{
int i = 1, j = 0;
nextval[1] = 0;
while (i < T[0])
if (j == 0 || T[i] == T[j])
{
++i;
++j;
if (T[i] != T[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
}
int Index_KMP(SString S, SString T, int pos, int next[])
{
int i = pos, j = 1;
while (i <= S[0] && j <= T[0])
if (j == 0 || S[i] == T[j])
{
++i;
++j;
}
else
j = next[j]; // 模式串向右移动
if (j > T[0]) // 匹配成功
return i - T[0];
else
return 0;
}
int main()
{
SString S;
StrAssign(S,"abcabaaccbabcccbabaacbacbaabcabaa") ;
SString T;
StrAssign(T,"abcabaa") ;
int *p = new int[T[0]+1];
get_nextval(T,p);
cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
return 0;
}