Pagini recente » Cod sursa (job #2974087) | Cod sursa (job #231632) | Cod sursa (job #1435969) | Cod sursa (job #1360063) | Cod sursa (job #1382441)
#include <fstream>
#include <cstring>
using namespace std;
ifstream r("strmatch.in");
ofstream w("strmatch.out");
int pi[2000002],d[2000002];
char x[2000002],y[2000002];
int n,m,nr,nrp;
void construct_pi(){
int k,i;
k=0;
pi[1]=0;
for (i=2;i<=n;i++){
while (k!=0&&x[i]!=x[k+1])
k=pi[k];
if (x[i]==x[k+1])
k++;
pi[i]=k;
}
}
int main(){
int k,i;
r>>(x+1);
r>>(y+1);
n=strlen(x+1);
m=strlen(y+1);
construct_pi();
k=0;
for (i=1;i<=m;i++){
while (k!=0 && y[i]!=x[k+1])
k=pi[k];
if (y[i]==x[k+1])
k++;
d[i]=k;
if (k==n)
nrp++;
}
w<<nrp<<"\n";
nr=0;
for (i=1;i<=m;i++)
if (d[i]==n){
w<<i-n<<" ";
nr++;
if (nr==1000)
break;
}
r.close();
w.close();
return 0;
}