Pagini recente » Cod sursa (job #1339802) | Cod sursa (job #2965232) | Cod sursa (job #305063) | Cod sursa (job #2695933) | Cod sursa (job #2304770)
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,l,p[DIM],sol,v[DIM],n,m;
char a[DIM],b[DIM];
void precalculare() {
l=0; p[1]=0;
for (i=2;i<=n;i++) {
while (l!=0&&b[i]!=b[l+1])
l=p[l];
if (b[i]==b[l+1])
l++;
p[i]=l;
}
}
int main() {
fin>>b+1; n=strlen(b+1);
fin>>a+1; m=strlen(a+1);
precalculare();
l=0;
for (i=1;i<=m;i++) {
while (l!=0&&a[i]!=b[l+1])
l=p[l];
if (a[i]==b[l+1])
l++;
if (l==n) {
sol++;
if (sol<=1000)
v[sol]=i-l+1;
l=p[l];
}
}
fout<<sol<<"\n";
for (i=1;i<=min(1000,sol);i++)
fout<<v[i]-1<<" ";
return 0;
}