Pagini recente » Cod sursa (job #2540795) | Cod sursa (job #558681) | Cod sursa (job #371991) | Cod sursa (job #3127498) | Cod sursa (job #3261959)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define minim(a,b) ((a<b) ? a:b)
#define nMax 2000005
int M,N;
char a[nMax], b[nMax];
int pi[nMax], pos[nMax];
void make_prefix()
{
int i,q=0;
for(i=2,pi[1]=0;i<=M;i++)
{
while(q&&a[q+1]!= a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
int main()
{
int i,q=0,n=0;
f>>a;
f>>b;
for (; (a[M] >= 'A' && a[M] <= 'Z') || (a[M] >= 'a' && a[M] <= 'z')|| (a[M] >= '0' && a[M] <= '9'); ++M);
for (; (b[N] >= 'A' && b[N] <= 'Z') || (b[N] >= 'a' && b[N] <= 'z')|| (b[N] >= '0' && b[N] <= '9'); ++N);
for(i=M;i>=0;i--) a[i]= a[i-1]; a[0]=' ';
for(i=N;i>=0;i--) b[i]= b[i-1]; b[0]=' ';
make_prefix();
for(i=1;i<=N;i++)
{
while(q&&a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==M)
{
q=pi[M];
++n;
if(n<=1000)
pos[n]=i-M;
}
}
g<<n<<endl;
for(i=1;i<=minim(n,1000);i++)
g<<pos[i]<<" ";
return 0;
}