Pagini recente » Cod sursa (job #1005567) | Cod sursa (job #1607264) | Cod sursa (job #1044377) | Cod sursa (job #2647519) | Cod sursa (job #2849728)
#include <fstream>
///#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int SIZE = 2e6+10;
ifstream in ("strmatch.in");
ofstream cout ("strmatch.out");
char s[SIZE], sf[SIZE];
int sn, sfn;
int pre[SIZE], pos[SIZE];
int cnt;
void prep()
{
int j=1;
for(int i=2; i<=sfn; i++)
if(sf[i]==sf[j]) {
pre[i]=j;
++j;
}
else j=1;
}
void kmp()
{
int j=0;
for(int i=1; i<=sn; i++) {
while(j && s[i]!=sf[j+1]) j=pre[j];
if(s[i]==sf[j+1]) {
++j;
if(j==sfn) {
++cnt;
if(cnt<=1000) pos[cnt]=i-sfn;
}
}
}
}
int main()
{
in>>(sf+1)>>(s+1);
sn = strlen(s+1);
sfn = strlen(sf+1);
prep();
kmp();
cout<<cnt<<'\n';
for(int i=1; i<=min(1000, cnt); i++)
cout<<pos[i]<<' ';
return 0;
}