Pagini recente » Cod sursa (job #570472) | Cod sursa (job #2599349) | Cod sursa (job #981822) | Cod sursa (job #2333138) | Cod sursa (job #2722588)
#include <fstream>
#include <cstring>
#define dim 2000010
using namespace std;
char a[dim];
char b[dim];
int sol[1010];
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) {
u++;
if (u<=1000) sol[u]=i-n;
}
}
fout<<u<<"\n";
for (i=1;i<=min(u,1000);i++) {
fout<<sol[i]<<" ";
}
/* for(i=1;i<=n;i++) {
fout<<p[i]<<" ";
} */
return 0;
}