Pagini recente » Cod sursa (job #2704121) | Cod sursa (job #1686709) | Cod sursa (job #3240446) | Cod sursa (job #1837921) | Cod sursa (job #751965)
Cod sursa(job #751965)
#include<fstream>
#define maxn 2000002
#define maxp 1024
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int m, n, p[maxn], poz[maxp], k=0;
char x[maxn], y[maxn];
inline int minim(int a, int b)
{return (((a)<(b)) ? (a):(b));
}
inline int is_alphanum(char c)
{return ((c>='A' && c<='Z') || (c>='a' && c<='z') || (c>='0' && c<='9')) ? (1):(0);
}
void make_prefix()
{p[1]=0;
for(int i=2, q=0; i<=m; i++)
{while(q && x[q+1]!=x[i])
q=p[q];
if(x[q+1]==x[i])
q++;
p[i]=q;
}
}
int main()
{f>>x>>y;
while(is_alphanum(x[m]))
m++;
while(is_alphanum(y[n]))
n++;
for(int i=m; i; i--)
x[i]=x[i-1];
for(int i=n; i; i--)
y[i]=y[i-1];
x[0]=y[0]=' ';
make_prefix();
for(int i=1, q=0; i<=n; i++)
{while(q && x[q+1]!=y[i])
q=p[q];
if(x[q+1]==y[i])
q++;
if(q==m)
{q=p[m];
k++;
if(k<=maxp)
poz[k]=i-m;
}
}
g<<k<<"\n";
for(int i=1; i<=minim(k, maxp); i++)
g<<poz[i]<<" ";
g<<"\n";
return 0;
}