Pagini recente » Cod sursa (job #470043) | Cod sursa (job #1723562) | Cod sursa (job #2904279) | Cod sursa (job #1499853) | Cod sursa (job #2717730)
#include <fstream>
#include <cstring>
#define dim 2000010
using namespace std;
char a[dim];
char b[dim];
int pat[dim];
int sol[1010];
int i,j,n,m,nr;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin>>a+1;
fin>>b+1;
m=strlen(a+1);
n=strlen(b+1);
for (i=2;i<=m;i++) {///creare prefix
if (a[i]==a[pat[i-1]+1]) {
pat[i]=pat[i-1]+1;
}
}
j=0;
for (i=1;i<=n;i++) {
while (j&&a[j+1]!=b[i]) {
j=pat[j];
}
if (a[j+1]==b[i]) {
j++;
}
if (j==m) {
nr++;
if (nr<=1000) sol[nr]=i-m;
j=pat[j];
}
}
fout<<nr<<"\n";
for (i=1;i<=min(nr,1000);i++) {
fout<<sol[i]<<" ";
}
/** for (i=1;i<=m;i++) {
fout<<pat[i]<<" ";
} **/
return 0;
}