Pagini recente » Cod sursa (job #1573269) | Cod sursa (job #1670917) | Cod sursa (job #3134716) | Cod sursa (job #1746374) | Cod sursa (job #2717705)
#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++) {
if (a[i]==a[pat[i-1]+1]) {
pat[i]=pat[i-1]+1;
}
}
for (i=1;i<=n;i++) {
if (a[j+1]==b[i]) {
j++;
}
else {
j=pat[j];
}
if (j==m) {
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<=n;i++) {
fout<<pat[i]<<" ";
} **/
return 0;
}