Pagini recente » Cod sursa (job #1589386) | Istoria paginii runda/einigeswanker | Cod sursa (job #274831) | Cod sursa (job #754680) | Cod sursa (job #1382201)
#include <fstream>
#include <cstring>
using namespace std;
ifstream r("strmatch.in");
ofstream w("strmatch.out");
long pi[200002],d[200002];
char x[200002],y[200002];
long n,m,nr,nrp;
void construct_pi(){
long 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(){
long 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;
}