#include
#include
#include
#include
#define KEYSIZE 256
void PreBmBc(char *x, int m, int *bc)
{
int i;
for(i=0; i
{
bc[i] = -1;
}
for(i=0; i
{
bc[x[i]] = i;
}
}
int PreBmGs(char *pat, int n, int *sf, int *sfl)
{
int m = n / 2;
int u = 0;
int i;
int j;
int k = 0;
for(i=0; i
{
sf[i] = -1;
sfl[i] = 0;
}
for(i=0; i
{
for(j=0; j
{
u = 1;
for(k=0; k<=i; k++)
{
if(pat[j+k] != pat[n-1-i+k])
{
u = 0;
break;
}
}
if(u)
{
sf[n-1-i] = j;
sfl[n-1-i] = i+1;
}
}
}
for(i=n-2; i>=0; i--)
{
if(sf[i+1] < i && sfl[i] < sfl[i+1])
{
sf[i] = sf[i+1];
sfl[i] = sfl[i+1];
}
}
for(i=0; i
{
if(sf[i] == -1)
{
sf[i] = n - 1;
}
else
{
sf[i] = n - sfl[i] - sf[i];
}
}
return 0;
}
int BM(char *str, int n, char *pat, int m, int *bc, int *sf)
{
int c, d;
int i = 0;
int j = m-1;
int k = 0;
int l = 0;
while(i+j < n)
{
if(str[i+j] != pat[j])
{
c = j - bc[str[i+j]];
d = 0;
if(j+1 < m)
{
d = sf[j+1];
}
i += (c > d ? c : d);
j = m - 1;
l++;
}
else
{
j--;
}
if(j == -1)
{
break;
}
}
if(j != -1)
{
return -1;
}
return i;
}
int main()
{
FILE *fp;
char str[4096] = "abcacabbcabccabc";
char pat[1024] = "your";
int bc[256];
int sf[256];
int sfl[256];
int n = strlen(str);
int m = strlen(pat);
int u;
int k = 0;
PreBmBc(pat, m, bc);
PreBmGs(pat, m, sf, sfl);
fp = fopen("1.txt", "r");
memset(str, 0x00, sizeof(str));
while(fgets(str, 2048, fp) != NULL)
{
n = strlen(str);
k++;
u = BM(str, n, pat, m, bc, sf);
if(u >= 0)
{
printf("%d\n", u);
}
memset(str, 0x00, sizeof(str));
}
fclose(fp);
return 0;
}