Pagini recente » Cod sursa (job #1338517) | Cod sursa (job #796728) | Cod sursa (job #2012888) | Cod sursa (job #526210) | Cod sursa (job #165015)
Cod sursa(job #165015)
#include<fstream>
using namespace std;
char a[2000002], b[2000002];
int m, n, lim, r[1024], pi[2000002];
void prefix(){
int i, k;
pi[1]=0;
k=0;
for(i=2;i<=m;i++){
while(k && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
k++;
pi[k]=k;
}
}
void match(){
int i, k;
k=0;
for(i=1;i<=n;i++){
while(k && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
if(k==m)
{
lim++;
k=pi[k];
if(lim<1001) r[lim]=i-m+1;
}
}
}
int main(){
ifstream f("strmatch.in");
f>>(a+1)>>(b+1);
f.close();
n=1;while(b[n]) n++; n--;
m=1; while(a[m]) m++; m--;
prefix();
match();
ofstream g("strmatch.out");
g<<lim<<'\n';
int i, min;
min=(1000<lim)?1001:(lim+1);
for(i=1;i<min;i++)
g<<r[i]<<' ';
g.close();
return 0;
}