Мой алгоритм выводит позицию первого вхождения подстроки в строке, а мне нужно, чтобы выводил позиции всех вхождений. Помогите пожалуйста!
| Код |
#include <cstdlib>
#include <iostream>
#include <string>
#define ALPHABET_LEN 255
#define NOT_FOUND patlen
#define max(a, b) ((a < b) ? b : a)
using namespace std;
void make_delta1 (int *delta1, char *pat, long int patlen)
{
int i;
for (i=0; i < ALPHABET_LEN; i++) delta1[i] = NOT_FOUND;
for (i=0; i < patlen-1; i++) delta1[pat[i]] = patlen-1-i;
}
int is_prefix (char *word, int wordlen, int pos)
{
int suffixlen = wordlen - pos;
for (int i = 0; i<suffixlen; i++)
{
if (word[i] != word[pos+i]) return 0;
}
return 1;
}
int suffix_length (char *word, int wordlen, int pos)
{
int i;
for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
return i;
}
void make_delta2(int *delta2, char *pat, long int patlen)
{
int last_prefix_index = patlen-1;
int p;
for (p=patlen-1; p>=0; p--)
{
if (is_prefix(pat, patlen, p+1)) last_prefix_index = p+1;
delta2[p] = last_prefix_index + (patlen-1 - p);
}
for (p=0; p < patlen-1; p++)
{
int slen = suffix_length(pat, patlen, p);
if (pat[p-slen]!=pat[patlen-1-slen]) delta2[patlen-1-slen]=patlen-1-p+slen;
}
}
int boyer_moore (char *string, char *pat)
{
long int stringlen = strlen(string);
long int patlen =strlen(pat);
int delta1[ALPHABET_LEN];
make_delta1(delta1, pat, patlen);
int *delta2 = new int [patlen * sizeof(int)];
make_delta2(delta2, pat, patlen);
int i = patlen-1;
while (i < stringlen)
{
int j = patlen-1;
while (j >= 0 && (string[i] == pat[j]))
{
--i; --j;
}
if (j < 0)
{
delete delta2;
return i+2;
int k=i+2;
for (int f=0;f<=k+1;f++)
string[f]=0;
}
i += max(delta1[string[i]], delta2[j]);
}
delete delta2;
return NULL;
}
int main()
{
char *string="ceea babc";
char *pattern="a";
long int stringlen = strlen(string);
for (int l=0;l<stringlen;l++)
{
cout << boyer_moore(string,pattern)<<" "<<endl;
}
return EXIT_SUCCESS;
}
|
|