Pagini recente » Cod sursa (job #915775) | Cod sursa (job #469775) | Cod sursa (job #3169371) | Cod sursa (job #968361) | Cod sursa (job #2722586)
#include <fstream>
#include <cstring>
#define dim 2000010
using namespace std;
char a[dim];
char b[dim];
int sol[dim];
int p[dim];
int i,j,n,m,u;
void prefix (char a[]) {
j=0;
for (i=2;a[i]!=0;i++) {
while (j&&a[i]!=a[j+1]) {
j=p[j];
}
if (a[i]==a[j+1]) {
p[i]=++j;
}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
prefix(a);
j=0;
for (i=1;i<=m;i++) {
while (j&&a[j+1]!=b[i]) {
j=p[j];
}
if (a[j+1]==b[i]) {
j++;
}
if (j==n) {
sol[++u]=i-n;
}
}
fout<<u<<"\n";
for (i=1;i<=u;i++) {
fout<<sol[i]<<" ";
}
/* for(i=1;i<=n;i++) {
fout<<p[i]<<" ";
} */
return 0;
}