Pagini recente » Cod sursa (job #1592330) | Cod sursa (job #2568264) | Cod sursa (job #1264550) | Cod sursa (job #1366568) | Cod sursa (job #2194915)
#include <fstream>
#include <cstring>
using namespace std;
char text[2000010],pat[2000010];
FILE *fin,*fout;
int table[256],n,m,i,j,sol[1010],nrSol;
int maxi(int a, int b)
{
return a>b ? a:b;
}
int mini(int a, int b)
{
return a<b ? a:b;
}
void read()
{
fin = fopen("strmatch.in","r");
fout = fopen("strmatch.out","w");
fscanf(fin,"%s",pat);
fscanf(fin,"%s",text);
}
void preProces(char* pat)
{
int len = m;
for (int i = 0; i<len ; i++)
{
table[pat[i]] = maxi(1,len-i-1);
}
}
void BM()
{
int nextstep = 0;
for (int i=0;i<=n-m;i+=nextstep)
{
nextstep = 0;
for (int j = m-1;j>=0;j--)
{
if (text[i+j]!=pat[j])
{
if (table[text[i+j]])
{
nextstep = table[text[i+j]];
break;
}
else
{
nextstep = m;
break;
}
}
}
if (!nextstep)
{
nrSol++;
nextstep = 1;
if (nrSol<=1000)
sol[nrSol] = i;
}
}
}
int main()
{
read();
n = strlen(text);
m = strlen(pat);
preProces(pat);
BM();
fprintf(fout,"%d\n",nrSol);
for (int i=1 ; i<=mini(nrSol,1000) ;i++ )
fprintf(fout,"%d ",sol[i]);
fprintf(fout,"\n");
return 0;
}