Pagini recente » Monitorul de evaluare | Diferente pentru utilizator/parket intre reviziile 7 si 8 | Monitorul de evaluare | Cod sursa (job #2288897)
#include <bits/stdc++.h>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,k,p[nmax],nr,v[1005];
char a[nmax],c[nmax];
int main() {
int i,j;
f.getline(c+1,nmax);
f.getline(a+1,nmax);
n=strlen(c+1);
m=strlen(a+1);
for (i=2;i<=n;i++) {
while (k!=0 && c[k+1]!=c[i]) k=p[k];
if (c[k+1]==c[i]) k++;
p[i]=k;
}
k=0;
for (i=1;i<=m;i++) {
while (k!=0 && c[k+1]!=a[i]) k=p[k];
if (c[k+1]==a[i]) k++;
if (k==n) {
nr++;
if (nr<=1000) v[nr]=i-n;
}
}
g<<nr<<'\n';
for (i=1;i<=min(nr,1000);i++) g<<v[i]<<' ';
return 0;
}